Answers.Body: <p>No, it will not converge in the general case (maybe it might in extremely convenient special cases, not sure, didn't think hard enough about that...). </p>
  
  <p>Practically everything in Reinforcement Learning theory (including convergence proofs) relies on the <strong>Markov property</strong>; the assumption that the current state <span class="math-container">$s_t$</span> includes all relevant information, that the history leading up to <span class="math-container">$s_t$</span> is no longer relevant. In your case, this property is violated; it is important to remember whether or not we visited <span class="math-container">$s$</span> more recently than <span class="math-container">$s'$</span>. </p>
  
  <p>I suppose if you "enhance" your states such that they include that piece of information, then it should converge again. This means that you'd essentially double your state-space. For every state that you have in your "normal" state space, you'd have to add a separate copy that would be used in cases where <span class="math-container">$s$</span> was visited more recently than <span class="math-container">$s'$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-07T10:06:42.860Z
Answers.Text: @Perissiane I can't really comment on that without specifics... maybe they "enhanced" the states as I described. Or maybe with "handle" they must mean "turns out to perform decently well empirically", which is of course very different from having a theoretical convergence proofs. Often when there are "mild" violations of things like the Markov property, most RL algorithms can still perform well empirically, it's just the theory that breaks down first.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-06T18:13:15.203Z
Answers.LastActivityDate: 2019-02-06T18:28:50.813Z
Answers.LastEditDate: 2019-02-06T18:28:50.813Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Imagine that the agent receives a positive reward upon reaching a state . Once the state  has been reached the positive reward associated with it vanishes and appears somewhere else in the state space, say at state ′. The reward associated to ′ also vanishes when the agent visits that state once and re-appears at state . This goes periodically forever. Will discounted Q-learning converge to the optimal policy in this setup? Is yes, is there any proof out there, I couldn't find anything.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-06T16:31:39.780Z
Comments.Text: "Once the state  has been reached the positive reward associated with it vanishes and appears somewhere else in the state space, say at state ′": why should the reward vanish? The reward is just a scalar value you receive from the environment after having performed an action. The reward can't really vanish. Maybe you mean the "return" or "value" of a state?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-06T16:32:30.763Z
Comments.Text: No, assume that the reward is dynamic and the environment gives the agent a positive scalar value only for the first visit.
Comments.UserDisplayName: Perissiane
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-06T16:35:56.987Z
Comments.Text: How "assume that the reward is dynamic and the environment gives the agent a positive scalar value only for the first visit." is related to your question? Actually, in your question, you're saying that "sometimes you receive a reward for entering state $s$ and sometimes for entering state $s'$". This can be just a regular scenario, if the environment is stochastic: in general, if the environment is stochastic, if you enter state s once and you receive a reward $r$, in future visits of the state $s$, the environment may give you different reward, say $r'$ (or $-r$)
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-02-06T17:10:40.093Z
Comments.Text: I should have been more clear: I meant that assume the agent visits state $s$ for the first time. The reward for this transition is positive. However, the agent will not receive any positive reward if it visits state $s$ for the second time and so on. The positive reward now is given to the agent if it visits state $s'$. Once the agent visits state $s'$ it gets a positive reward and the positive reward goes back to state $s$. So, somehow the agent has to learn a cycle behavior between states $s$ and $s'$.
Comments.UserDisplayName: Perissiane
Tags: <reinforcement-learning><q-learning>
Title: Will Q-learning converge to the optimal state-action function when the reward periodically changes?
UserDisplayName: Perissiane
ThreadText: # Will Q-learning converge to the optimal state-action function when the reward periodically changes?
  
  (Asked by: username_0 on 2019-02-06)
  
  Imagine that the agent receives a positive reward upon reaching a state . Once the state has been reached the positive reward associated with it vanishes and appears somewhere else in the state space, say at state ′. The reward associated to ′ also vanishes when the agent visits that state once and re-appears at state . This goes periodically forever. Will discounted Q-learning converge to the optimal policy in this setup? Is yes, is there any proof out there, I couldn't find anything.
  
  **Tags:** reinforcement-learning, q-learning
  > **Comments:**
  > **username_1**: "Once the state  has been reached the positive reward associated with it vanishes and appears somewhere else in the state space, say at state ′": why should the reward vanish? The reward is just a scalar value you receive from the environment after having performed an action. The reward can't really vanish. Maybe you mean the "return" or "value" of a state?  
  > **username_0**: No, assume that the reward is dynamic and the environment gives the agent a positive scalar value only for the first visit.  
  > **username_1**: How "assume that the reward is dynamic and the environment gives the agent a positive scalar value only for the first visit." is related to your question? Actually, in your question, you're saying that "sometimes you receive a reward for entering state $s$ and sometimes for entering state $s'$". This can be just a regular scenario, if the environment is stochastic: in general, if the environment is stochastic, if you enter state s once and you receive a reward $r$, in future visits of the state $s$, the environment may give you different reward, say $r'$ (or $-r$)  
  > **username_0**: I should have been more clear: I meant that assume the agent visits state $s$ for the first time. The reward for this transition is positive. However, the agent will not receive any positive reward if it visits state $s$ for the second time and so on. The positive reward now is given to the agent if it visits state $s'$. Once the agent visits state $s'$ it gets a positive reward and the positive reward goes back to state $s$. So, somehow the agent has to learn a cycle behavior between states $s$ and $s'$.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-02-06. Score: 3 | Accepted answer
  
  No, it will not converge in the general case (maybe it might in extremely convenient special cases, not sure, didn't think hard enough about that...).
  
  Practically everything in Reinforcement Learning theory (including convergence proofs) relies on the **Markov property**; the assumption that the current state $s\_t$ includes all relevant information, that the history leading up to $s\_t$ is no longer relevant. In your case, this property is violated; it is important to remember whether or not we visited $s$ more recently than $s'$.
  
  I suppose if you "enhance" your states such that they include that piece of information, then it should converge again. This means that you'd essentially double your state-space. For every state that you have in your "normal" state space, you'd have to add a separate copy that would be used in cases where $s$ was visited more recently than $s'$.
  
  > **Comments:**
  > **username_2**: @Perissiane I can't really comment on that without specifics... maybe they "enhanced" the states as I described. Or maybe with "handle" they must mean "turns out to perform decently well empirically", which is of course very different from having a theoretical convergence proofs. Often when there are "mild" violations of things like the Markov property, most RL algorithms can still perform well empirically, it's just the theory that breaks down first.  
  
  ---
  
  