On Q-learning Convergence for Non-Markov Decision Processes

By Sultan Javed Majeed, Marcus Hutter. 2018

44 citations recorded by the source corpus.

Temporal-difference (TD) learning is an attractive, computationally efficient framework for model- free reinforcement learning. Q-learning is one of the most widely used TD learning technique that enables an agent to learn the optimal action-value function, i.e. Q-value function. Contrary to its widespread use, Q-learning has only been proven to converge on Markov Decision Processes (MDPs) and Q-uniform abstractions of finite-state MDPs. On the other hand, most real-world problems are inherently non-Markovian: the full true state of the environment is not revealed by recent observations. In this paper, we investigate the behavior of Q-learning when applied to non-MDP and non-ergodic domains which may have infinitely many underlying states. We prove that the convergence guarantee of Q-learning can be extended to a class of such non-MDP problems, in particular, to some non-stationary domains. We show that state-uniformity of the optimal Q-value function is a necessary and sufficient condition for Q-learning to converge even in the case of infinitely many internal states.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Matthew Riemer
2. Irina Rish
3. Miao Liu
4. Khimya Khetarpal
5. G. Tesauro
6. Jonathan P. How
7. Doina Precup
8. Sergey Levine

In Computational Theory and Mathematics

1. Khimya Khetarpal
2. Matthew Riemer
3. Miao Liu
4. G. Tesauro
5. Doina Precup
6. Jonathan P. How
7. Irina Rish
8. Michael L. Littman

In Molecular Biology

1. Doina Precup
2. Irina Rish
3. Khimya Khetarpal
4. Matthew Riemer

Citations in the corpus

• Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Bayesian RL: On the other hand, a more ambitious approach would be to try to learn a belief of the unobserved task state directly from the history of environment interactions (Li et al., 2009; Hernandez-Leal, Zhan, Taylor, Sucar, and de Cote, 2017; Majeed and Hutter, 2018).”
• Context-Specific Representation Abstraction for Deep Option Learning (2021, background): “Under the state uniformity assumption discussed in Majeed and Hutter (2018), we assume the optimal policy network based on the agent’s history is equivalent to the network conditioned on the true state space.”