  We study the interplay of two interacting discrete time quantum walks in the
presence of disorder. Each walk is described by a Floquet unitary map defined
on a chain of two-level systems. Strong disorder induces a novel Anderson
localization phase with a gapless Floquet spectrum and one unique localization
length $\xi_1$ for all eigenstates for noninteracting walks. We add a local
contact interaction which is parametrized by a phase shift $\gamma$. A wave
packet is spreading subdiffusively beyond the bounds set by $\xi_1$ and
saturates at a new length scale $\xi_2 \gg \xi_1$. In particular we find $\xi_2
\sim \xi_1^{1.2}$ for $\gamma=\pi$. We observe a nontrivial dependence of
$\xi_2$ on $\gamma$, with a maximum value observed for $\gamma$-values which
are shifted away from the expected strongest interaction case $\gamma=\pi$. The
novel Anderson localization regime violates single parameter scaling for both
interacting and noninteracting walks.
