# Will Q-learning converge to the optimal state-action function when the reward periodically changes?

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.

• "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? – nbro Feb 6 '19 at 16:31
• No, assume that the reward is dynamic and the environment gives the agent a positive scalar value only for the first visit. – Perissiane Feb 6 '19 at 16:32
• 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$) – nbro Feb 6 '19 at 16:35
• 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'$. – Perissiane Feb 6 '19 at 17:10

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'$$.