I finally found a complete answer to my question. My sequence is not the same thing as the convergents of the standard continued fraction of $\theta$ ; indeed, many terms in my sequence are not convergents and many convergents are not in my sequence. However, the two sequences share near-identical properties as we are going to see.
For any $m\geq 1$, enote by $l_m$ ($u_m$, respectively) the largest (smallest) fraction with denominator $\leq m$ that is smaller (larger) than $\theta$. Thus the set $\lbrace l_m | m \geq 1\rbrace$ is the same thing as the set $\lbrace \frac{a_n}{b_n} | n \geq 1\rbrace$, and for every $n$ we have $\frac{a_n}{b_n}=l_{b_n}$. On the other side of $\theta$, $u_{b_n}$ can be written as a reduced fraction $\frac{c_n}{d_n}$. It is well-known that $b_nc_n-a_nd_n=1$. To find the next term $\frac{a_{n+1}}{b_{n+1}}$, we use mediants : let $v_0=\frac{c_n}{d_n}$, and for $k \geq 1$ let $v_{k}$ be the mediant of $v_{k-1}$ and $\frac{a_n}{b_n}$. Then one has $v_k=\frac{c_n+ka_n}{d_n+kb_n}$ for all $k$, and there is a unique $k_n$ such that $v_{k_n} > \theta > v_{k_n+1}$. Then the next pair of near-values around $\theta$, $(\frac{a_{n+1}}{b_{n+1}},\frac{c_{n+1}}{d_{n+1}})$ is exactly $(v_{k_{n+1}},v_{k_n})$. We deduce the recurrence formulas
$ a_{n+1}=c_n+(k_{n}+1)a_n \\ b_{n+1}=d_n+(k_{n}+1)b_n \\ c_{n+1}=c_n+k_{n}a_n \\ d_{n+1}=d_n+k_{n}b_n \\ $
which can be rewritten more elegantly as a matrix equality : if we put
$ K_n= \left( \begin{matrix} k_n+1 & 1 \\ k_n & 1 \end{matrix} \right), M_n= \left( \begin{matrix} a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} \right) $ then we have $M_{n+1}=K_nM_n$ for all $n\geq 1$. Also, $k_n$ can be written as $\lfloor \rho_n \rfloor$, where $\rho_n=\frac{c_n-d_n\theta}{b_n\theta-a_n}$. If we put
$ \left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \star x=\frac{cx-d}{bx-a}, $ then this defines a group action of $GL_2({\mathbb Q})$ on $\mathbb Q$ : $A \star (B \star x)=(AB) \star x$ for any matrices $A,B$ and any $x\in {\mathbb Q}$. We deduce $ \rho_{n+1}=M_{n+1}\star\theta=K_nM_n \star \theta=K_n \star \rho_n $ In other words, the sequence $(\rho_n)$ satisfies the recurrence relation
$ \rho_{n+1}=f(\rho_n), \ {\rm with} \ f(x)=\frac{x-\lfloor x \rfloor}{\lceil x\rceil-x} $
If $\theta$ is a quadratic irrational, it can be written in the familiar "Legendre" form $\frac{p+\sqrt{D}}{q}$ where $p,q,D$ are integers with $D$ a nonsquare, and $q$ divides $D-p^2$. Then, by induction, each $\rho_n$ is again of the form $\frac{p_n+\sqrt{D}}{q_n}$ where $p_n$ and $q_n$ are integers and $q_n$ divides $D-p_n^2$. So $r_n=\frac{D-p_n^2}{q_n}$ is an integer, and we have $|q_nr_n| \leq |D|$, $|q_n| \leq D, |r_n| \leq |D|, |p_n^2| \leq |D|+|q_nr_n| \leq |D|+|D|^2$. So there are only finitely many possible values for the pair $(p,q)$, so the sequence $(\rho_n)$ takes its values in a finite set. Since it also satisfies $\rho_{n+1}=f(\rho_n)$, it is eventually periodic. Then $(k_n)$ is also eventually periodic, and it is easily deduced that the vector $(a_n,b_n,c_n,d_n)$ satisfies a linear recurrence relation (for more details see the article linked by Aryabhata in the comments).