# Approximate information state based convergence analysis of recurrent Q-learning

arXiv: https://arxiv.org/abs/2306.05991 · HTML: https://mlsanity.com/paper/2306.05991/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 29 of 29)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [DeepMind Control Suite](https://mlsanity.com/paper/1801.00690/) (2018)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Prioritized Level Replay](https://mlsanity.com/paper/2010.03934/) (2020)
- [InfoBot: Transfer and Exploration via the Information Bottleneck](https://mlsanity.com/paper/1901.10902/) (2019)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Interesting Object, Curious Agent: Learning Task-Agnostic Exploration](https://mlsanity.com/paper/2111.13119/) (2021)
- [BeBold: Exploration Beyond the Boundary of Explored Regions](https://mlsanity.com/paper/2012.08621/) (2020)
- [Deep Attention Recurrent Q-Network](https://mlsanity.com/paper/1512.01693/) (2015)
- [How to Stay Curious while Avoiding Noisy TVs using Aleatoric Uncertainty Estimation](https://mlsanity.com/paper/2102.04399/) (2021)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks](https://mlsanity.com/paper/1602.02672/) (2016)
- [Recurrent Reinforcement Learning: A Hybrid Approach](https://mlsanity.com/paper/1509.03044/) (2015)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Learning to predict where to look in interactive environments using deep recurrent q-learning](https://mlsanity.com/paper/1612.05753/) (2016)
- [On the Complexity of Exploration in Goal-Driven Navigation](https://mlsanity.com/paper/1811.06889/) (2018)
- [Autonomous quadrotor obstacle avoidance based on dueling double deep recurrent Q-learning with monocular vision](https://mlsanity.com/paper/2002.03510/) (2020)

## Built on by (most cited first, 5 of 5)

- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Improving Intrinsic Exploration by Creating Stationary Objectives](https://mlsanity.com/paper/2310.18144/) (2023)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)

## Abstract (arXiv)

In spite of the large literature on reinforcement learning (RL) algorithms for partially observable Markov decision processes (POMDPs), a complete theoretical understanding is still lacking. In a partially observable setting, the history of data available to the agent increases over time so most practical algorithms either truncate the history to a finite window or compress it using a recurrent neural network leading to an agent state that is non-Markovian. In this paper, it is shown that in spite of the lack of the Markov property, recurrent Q-learning (RQL) converges in the tabular setting. Moreover, it is shown that the quality of the converged limit depends on the quality of the representation which is quantified in terms of what is known as an approximate information state (AIS). Based on this characterization of the approximation error, a variant of RQL with AIS losses is presented. This variant performs better than a strong baseline for RQL that does not use AIS losses. It is demonstrated that there is a strong correlation between the performance of RQL over time and the loss associated with the AIS representation.