This is comes from cs2852023Fall, hw3. I'm learning RL by myself and I cann't find answers related to this question. Althrough it's from a homework, I believe it would be beneficial to solve the question and get a deeper understanding for q-learning. The resource could be found in https://rail.eecs.berkeley.edu/deeprlcourse/.
Backgorund
Consider the N-step variant of Q-learning described.
\begin{align} y_{i,j} \gets (\sum_{t'=t}^{t+N-1 }\gamma^{t'-t}r_{j,t'} + \gamma^N \max_{a_{j, t+N}}Q_{\phi_{k}}(s_{j,t+N}, a_{j,t+N}) (1)\\ \phi_{k+1} \gets \arg\min_{\phi\in\Phi}\sum_{j,t}(y_{j,t} - Q_{\phi}(s_{j,t}, a_{j,t}))^2 (2) \end{align} In these equations, $j$ indicates an index in the replay buffer of trajectories $𝓓_{k}$. We first roll out a batch of B trajectories to update $𝓓_{k}$ and compute the target values in (1). We then fit $Q_{\phi_{k+1}}$ to these target values with (2). After estimating $Q_{\phi_{k+1}}$, we can then update the policy through an argmax: $$ \pi_{k+1}(a_t | s_t) \gets \begin{cases} & 1\text{ if } a_{t} = \arg\max_{a_{t}}Q_{\phi_{k+1}}(s_{t}, a_{t})\\ & 0\text { otherwise } \end{cases}(3) $$
We repeat the steps in eqs.(1) to (3) K times to improve the policy. In this question, you will analyze some properties of the algoriyhm, which is summarized in Algorithm 1.
Question
At each iteraction of the algorithm above after update from eq.(2), $Q_{\phi_{k}}$ can be viewed as an estimate of the true optimal $Q^\star$. Consider the following statements:
I. $Q_{\phi_{k+1}}$ is an unbiased estimate of the $Q$ function of the last policy, $Q^{\pi_{k}}.$
II. As $k\to\infty$ for some fixed $B$ (replay_buffer), $Q^{\pi_{k}}$ is an unbiased estimate of $Q^{\star}$, i.e., $\lim_{k\to\infty}\mathbb{E}[Q_{\phi_{k}}(s,q) - Q^{\star}(s,a)] = 0$
III. In the limit of infinite iterations and data we recover the optmimal $Q^{\star}$, i.e., $\lim_{k,B\to\infty}\mathbb{E}[||Q_{\phi_{k}} - Q^{\star}||] = 0$
We make the additional assumptions:
- The state and action spaces are finite.
- Every batch contains at least one experience for each action taken in each state.
- In the tabular setting, $Q_{\phi_{k}}$ can express any function, i.e., ${Q_{\phi_{k}}:\phi\in\Phi}=\mathbb{R}^{S \times A}$
When updating the buffer $𝓓_{k}$ with $B$, we say:
- When learning on-policy, $𝓓_{k}$ is set to contain only the set of $B$ new rollouts of $\pi$ (so $|𝓓_{k} = B|$). Thus, we only train on rollouts from the current policy
- When learning off-policy, we use a fixed dataset $𝓓_{k} = 𝓓$ of $B$ trajectories from another policy $\pi'$.
Indicate which of the statements I-III always hold in the following cases. \begin{align} 1. &\text {N = 1 and... }&I\qquad &II\qquad &III\\ &a. on-policy in tablular setting. &\Box\qquad &\Box\qquad &\Box \\ &b. off-policy in tabular setting.&\Box\qquad &\Box\qquad &\Box \\ 2. &\text { N > 1 and...}\\ &a. on-policy in tablular setting.&\Box\qquad &\Box\qquad &\Box \\ &b. off-policy in tabular setting.&\Box\qquad &\Box\qquad &\Box \\ 3. &\text {In the limite as $N\to\infty$ and...}\\ &a. on-policy in tablular setting.&\Box\qquad &\Box\qquad &\Box \\ &b. off-policy in tabular setting.&\Box\qquad &\Box\qquad &\Box \\ \end{align}
My Understanding
- When N = 1
- I: $ Q_{\phi_{k+1}}(s, a)=r(s,a) + \gamma \max_{a}Q_{\phi_{k}}(s_{t+1}, a_{t+1}) $, which is the Q function of the last policy, so this is the unbiased estimate of last policy?
- II: Because of the contraction of Bellman operator, and the expression of Q is suffcient for Q value function, this is also right?
- III: Statement is also right because of the contraction of Bellman Operator.
