  By a theorem of Gordon and Hedenmalm, $\varphi$ generates a bounded
composition operator on the Hilbert space $\mathscr{H}^2$ of Dirichlet series
$\sum_n b_n n^{-s}$ with square-summable coefficients $b_n$ if and only if
$\varphi(s)=c_0 s+\psi(s)$, where $c_0$ is a nonnegative integer and $\psi$ a
Dirichlet series with the following mapping properties: $\psi$ maps the right
half-plane into the half-plane $\operatorname{Re} s >1/2$ if $c_0=0$ and is
either identically zero or maps the right half-plane into itself if $c_0$ is
positive. It is shown that the $n$th approximation numbers of bounded
composition operators on $\mathscr{H}^2$ are bounded below by a constant times
$r^n$ for some $0<r<1$ when $c_0=0$ and bounded below by a constant times
$n^{-A}$ for some $A>0$ when $c_0$ is positive. Both results are best possible.
The case when $c_0=0$, $\psi$ is bounded and smooth up to the boundary of the
right half-plane, and $\sup \operatorname{Re} \psi=1/2$, is discussed in depth;
it includes examples of non-compact operators as well as operators belonging to
all Schatten classes $S_p$. For $\varphi(s)=c_1+\sum_{j=1}^d c_{q_j} q_j^{-s}$
with $q_j$ independent integers, it is shown that the $n$th approximation
number behaves as $n^{-(d-1)/2}$, possibly up to a factor $(\log n)^{(d-1)/2}$.
Estimates rely mainly on a general Hilbert space method involving finite linear
combinations of reproducing kernels. A key role is played by a recently
developed interpolation method for $\mathscr{H}^2$ using estimates of solutions
of the $\bar{\partial}$ equation. Finally, by a transference principle from
$H^2$ of the unit disc, explicit examples of compact composition operators with
approximation numbers decaying at essentially any sub-exponential rate can be
displayed.
