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