  We report on observations of spin dynamics in single Yb$^+$ ions immersed in
a cold cloud of spin-polarized $^6$Li atoms. This species combination has been
proposed to be the most suitable system to reach the quantum regime in atom-ion
experiments. For $^{174}$Yb$^+$, we find that the atomic bath polarizes the
spin of the ion by 93(4)\,\% after a few Langevin collisions, pointing to
strong spin-exchange rates. For the hyperfine ground states of $^{171}$Yb$^+$,
we also find strong rates towards spin polarization. However, relaxation
towards the $F=0$ ground state occurs after 7.7(1.5) Langevin collisions. We
investigate spin impurity atoms as possible source of apparent spin-relaxation
leading us to interpret the observed spin-relaxation rates as an upper limit.
Using ab initio electronic structure and quantum scattering calculations, we
explain the observed rates and analyze their implications for the possible
observation of Feshbach resonances between atoms and ions once the quantum
regime is reached.
