> For the complete documentation index, see [llms.txt](https://drdh.gitbook.io/rl/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://drdh.gitbook.io/rl/deep-rl-course/value-function-methods/q-iteration.md).

# Q iteration

## Fitted Q-iteration

What if we don't know the transition dynamics? Use Q-values and fit Q function instead of V

> Fitted Q-iteration algorithm:
>
> repeat until converge:
>
> \====1: set $$y\_i\leftarrow r(s\_i,a\_i)+\gamma \max\_{a'}Q\_\phi(s'\_i,a'\_i)$$
>
> \====2: set $$\phi\leftarrow \arg\min\_\phi\frac{1}{2}\sum\_i|Q\_\phi(s\_i,a\_i)-y\_i|^2$$

**+:** works even for off-policy samples (unlike actor-critic)

**+:** only one network, no high-variance policy gradient

**-:** no convergence guarantees for non-linear function approximation

> Full fitted Q-iteration algorithm:
>
> repeat until converge:
>
> \====1: collect dataset $${(s\_i,a\_i,s'\_i,r\_i}$$ using some policy; (dataset size N, collection policy)
>
> \====repeat K times; (iterations K)
>
> \======== 2: set $$y\_i\leftarrow r(s\_i,a\_i)+\gamma \max\_{a'}Q\_\phi(s'\_i,a'\_i)$$
>
> \========3: set $$\phi\leftarrow \arg\min\_\phi\frac{1}{2}\sum\_i|Q\_\phi(s\_i,a\_i)-y\_i|^2$$ ; (gradient steps S)

## Why off-policy

Given $$s$$ and $$a$$, transition is independent of $$\pi$$

![Q-Iteration,off-policy](/files/-Lo5fhX8cxoiHpNdmqPd)

## Optimize what

In algorithm line 2, the max trick improves the policy (tabular case). And if we denote dataset distribution as $$\beta$$, we have error:

$$
\mathcal{E}=\frac{1}{2}\mathbb{E}*{(s,a)\sim\beta}\left\[Q*\phi(s,a)-\left\[r(s,a)+\gamma\max\_{a'}Q\_\phi(s',a')\right]    \right]
$$

If $$\mathcal{E}=0$$, then $$Q\_\phi(s,a)=r(s,a)+\gamma\max\_{a'}Q\_\phi(s',a')$$, which is the optimal Q-function, corresponding to optimal policy $$\pi'$$. But when we leave the tabular case and use neural network function approximation, most guarantee are lost.

## Online Q-iteration

Set $$N=1,K=1$$

> Online Q-iteration algorithm:
>
> repeat until converge:
>
> \====1: collect dataset $${(s\_i,a\_i,s'\_i,r\_i}$$ using some policy; (collection policy)
>
> \====2: set $$y\_i\leftarrow r(s\_i,a\_i)+\gamma \max\_{a'}Q\_\phi(s'\_i,a'\_i)$$
>
> \====3: set $$\phi\leftarrow \phi-\alpha\frac{dQ\_\phi}{d}(s\_i,a\_i)(Q\_\phi(s\_i,a\_i)-y\_i)$$ ; (gradient steps S)

## Exploration

Just using the final policy, which is deterministic, is a bad idea for step 1 to collect samples, because of exploration-exploitation problem. In general, there are other choices, since Q-iteration is a off-policy algorithm, such as:

**epsilon-greedy:**

$$
\pi(a\_t|s\_t)=
\begin{cases}
1-\epsilon &\text{if }a\_t=\arg\max\_{a\_t}Q\_\phi(s\_t,a\_t)\\
\epsilon/(|\mathcal{A}|-1)&\text{otherwise}
\end{cases}
$$

**Boltzmann exploration:**

$$
\pi(a\_t|s\_t)\propto \exp(Q\_\phi(s\_t,a\_t))
$$