Body: <p>I thought about an algorithm that twists the standard Q-learning slightly, but I am not sure whether convergence to the optimal Q-value could be guaranteed. </p>
  
  <p>The algorithm starts with an initial policy. 
  Within each episode, the algorithm conducts policy evaluation and does NOT update the policy. 
  Once the episode is done, the policy is updated using the greedy policy based on the current learnt Q-values.
  The process then repeats. I attached the algorithm as a picture.</p>
  
  <p>Just to emphasize that the updating policy does not change within each episode. The policy at each state is updated AFTER one episode is done, using the Q-tables. </p>
  
  <p>Has anyone seen this kind of Q-learning before? If so, could you please kindly guide me to some resources regarding the convergence? Thank you!</p>
  
  <p><a href="https://i.sstatic.net/54ynY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/54ynY.png" alt="enter image description here"></a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T23:20:37.867Z
Comments.Text: It's on-policy generalised policy iteration as written - kind of a hybrid of Monte Carlo control and SARSA - so I am surprised to see it called Q learning. Also, no exploration, which could be a weakness in some environments. Unfortunately I have not seen it before and would not know where to find convergence resources. Could you perhaps link to where you found it, because that may give some clues?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T23:32:05.653Z
Comments.Text: @NeilSlater Thanks for the comment. This is what I had in mind and had it written down, so I do not have a link. As for no exploration, I think the action selection here is not a big deal. One can just replace the sampling with an epsilon greedy selection. Also, could you please explain why this thing looks like a SARSA?
Comments.UserDisplayName: Lyapunov1729
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T23:35:35.633Z
Comments.Text: To make it off-policy you could change the Q value update step to take a max over possible actions in $s_{t+1}$ instead of making the on-policy update. Doesn't fix the lack of exploration, but does mean you would be estimating a different target polciy from current behaviour policy.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-22T23:37:36.183Z
Comments.Text: Yes it would be simple enough to have the behaviour policy as epsilon greedy. I suggest you write it like that though, because it is an important detail if you want to talk about convergence. Without exploration, convergence guarantees will be weaker
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-23T08:34:48.207Z
Comments.Text: Thanks for the update. The new algorithm is essentially Q learning with separate batched evaluation steps and policy update steps. Could you clarity what the $\epsilon$-greedy is evaluated over - is the greeedy action considered to be $\text{argmax}_a Q_t(s_t, a)$ or is it $\pi_i(s_t)$? This will make a difference to speed of convergence in some cases.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-23T12:56:04.500Z
Comments.Text: @NeilSlater We can use either. Personally, I don't care about convergence rate or sample complexity for now, I just want to know regarding convergence.
Comments.UserDisplayName: Lyapunov1729
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-23T13:39:28.483Z
Comments.Text: I suggest pick one in the algorithm, to make it concrete what the behaviour policy is based on. Although *I* might think it only affects convergence rate, it may actually affect convergence guarantees too. These kinds of details can be important.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><q-learning><convergence>
Title: Convergence of a delayed policy update Q-learning
UserDisplayName: Lyapunov1729
ThreadText: # Convergence of a delayed policy update Q-learning
  
  (Asked by: username_0 on 2020-05-22)
  
  I thought about an algorithm that twists the standard Q-learning slightly, but I am not sure whether convergence to the optimal Q-value could be guaranteed.
  
  The algorithm starts with an initial policy.
  Within each episode, the algorithm conducts policy evaluation and does NOT update the policy.
  Once the episode is done, the policy is updated using the greedy policy based on the current learnt Q-values.
  The process then repeats. I attached the algorithm as a picture.
  
  Just to emphasize that the updating policy does not change within each episode. The policy at each state is updated AFTER one episode is done, using the Q-tables.
  
  Has anyone seen this kind of Q-learning before? If so, could you please kindly guide me to some resources regarding the convergence? Thank you!
  
  [![enter image description here](https://i.sstatic.net/54ynY.png)](https://i.sstatic.net/54ynY.png)
  
  **Tags:** reinforcement-learning, q-learning, convergence
  
  > **Comments:**
  > **username_1**: It's on-policy generalised policy iteration as written - kind of a hybrid of Monte Carlo control and SARSA - so I am surprised to see it called Q learning. Also, no exploration, which could be a weakness in some environments. Unfortunately I have not seen it before and would not know where to find convergence resources. Could you perhaps link to where you found it, because that may give some clues?  
  > **username_0**: @username_1 Thanks for the comment. This is what I had in mind and had it written down, so I do not have a link. As for no exploration, I think the action selection here is not a big deal. One can just replace the sampling with an epsilon greedy selection. Also, could you please explain why this thing looks like a SARSA?  
  > **username_1**: To make it off-policy you could change the Q value update step to take a max over possible actions in $s_{t+1}$ instead of making the on-policy update. Doesn't fix the lack of exploration, but does mean you would be estimating a different target polciy from current behaviour policy.  
  > **username_1**: Yes it would be simple enough to have the behaviour policy as epsilon greedy. I suggest you write it like that though, because it is an important detail if you want to talk about convergence. Without exploration, convergence guarantees will be weaker  
  > **username_1**: Thanks for the update. The new algorithm is essentially Q learning with separate batched evaluation steps and policy update steps. Could you clarity what the $\epsilon$-greedy is evaluated over - is the greeedy action considered to be $\text{argmax}_a Q_t(s_t, a)$ or is it $\pi_i(s_t)$? This will make a difference to speed of convergence in some cases.  
  > **username_0**: @username_1 We can use either. Personally, I don't care about convergence rate or sample complexity for now, I just want to know regarding convergence.  
  > **username_1**: I suggest pick one in the algorithm, to make it concrete what the behaviour policy is based on. Although *I* might think it only affects convergence rate, it may actually affect convergence guarantees too. These kinds of details can be important.  
  
  ---
  
  ## 0 answers
  
  