Let's define two auxiliary sequences $c_n=a_{n+2}-a_{n+1}-2$ and $d_n=b_{n+2}-b_{n+1}$ for $n\geq 1$. The sequence $c_n$ takes values in $\{0,1,2,3\}$ and $b_n$ takes values in $\{1,2\}$.

The sequence $c_n$ starts: $1,1,1,1,3,0,\dots$ and $d_n$ starts: $1,1,1,2,1,2,1,\dots$. 

We know how to get from $d_n$ to $c_n$ with the relation $c_n=2d_{n-1}-d_{n-2}$. There is also a nice way to build $d_n$ from $c_n$ with a substitution step:
> Suppose we have the first $m$ terms of $c_n$. If we perform the substitutions
$0\to 2,1\to 21,2\to 211,3\to 2111$ and append $1,1,1$ as a prefix, we will obtain the first $m'=3+m+\sum_{n=1}^m c_n$ terms of $d_n$. Their sum is $\sum_{n=1}^{m'}d_n=3+2m+\sum_{n=1}^m c_n$.

Let's denote $\sum_{n=1}^m c_n=\sqrt{2}m+\epsilon_m$. Since $\sum_{n=1}^m c_n=a_{m+2}-2(m+2)-5$, your conjecture can be rephrased as
$$-2.172\approx2\sqrt2-5\le \epsilon_m\le 2\sqrt2-2\approx 0.828$$

I'm writing an argument to show that $\epsilon_m$ is bounded, but I get slightly worse constants. Let $f_1$ be some arbitrary natural number. Define $f_2$ to be the smallest natural number for which $\alpha =4+f_2+\sum_{n=1}^{f_2}c_n-f_1\geq 0$. Notice that $\alpha\le 3$. We can write
$$\sqrt{2}f_1+\epsilon_{f_1}=d_{f_1-1}+3+2f_2+\sqrt{2}f_2+\epsilon_{f_2}-\alpha$$
and
$$f_1=4+f_2+\sqrt{2}f_2+\epsilon_{f_2}-\alpha$$
So we get 
$$\epsilon_{f_1}=d_{f_1-1}-1-(\sqrt2-1)(4+\epsilon_{f_2}-\alpha).$$
Since $d_{f_1-1}\in [1,2]$ and $\alpha\in [0,3]$ this gives
$$\epsilon_m\in \left[\frac{\sqrt{2}-6}{2},\frac{5\sqrt{2}-4}{2}\right]\approx [-2.293,1.535]$$
for all $m$. (One can check that if $\epsilon_{f_2}$ belongs to this interval then so must $\epsilon_{f_1}$ and use strong induction.)