# Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 26 Dec 2021.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Exact Reduction of Huge Action Spaces in General Reinforcement Learning](https://mlsanity.com/paper/2012.10200/) (2020)
- [Selecting the State-Representation in Reinforcement Learning](https://mlsanity.com/paper/1302.2552/) (2013)
- [Performance Guarantees for Homomorphisms Beyond Markov Decision Processes](https://mlsanity.com/paper/1811.03895/) (2018)
- [Conditions on Features for Temporal Difference-Like Methods to Converge](https://mlsanity.com/paper/1905.11702/) (2019)

## Abstract (arXiv)

The field of General Reinforcement Learning (GRL) formulates the problem of sequential decision-making from ground up. The history of interaction constitutes a "ground" state of the system, which never repeats. On the one hand, this generality allows GRL to model almost every domain possible, e.g. Bandits, MDPs, POMDPs, PSRs, and history-based environments. On the other hand, in general, the near-optimal policies in GRL are functions of complete history, which hinders not only learning but also planning in GRL. The usual way around for the planning part is that the agent is given a Markovian abstraction of the underlying process. So, it can use any MDP planning algorithm to find a near-optimal policy. The Extreme State Aggregation (ESA) framework has extended this idea to non-Markovian abstractions without compromising on the possibility of planning through a (surrogate) MDP. A distinguishing feature of ESA is that it proves an upper bound of Oleft(varepsilon-A · (1-γ)-2Aright) on the number of states required for the surrogate MDP (where A is the number of actions, γ is the discount-factor, and varepsilon is the optimality-gap) which holds uniformly for all domains. While the possibility of a universal bound is quite remarkable, we show that this bound is very loose. We propose a novel non-MDP abstraction which allows for a much better upper bound of Oleft(varepsilon-1 · (1-γ)-2 · A · 2Aright). Furthermore, we show that this bound can be improved further to Oleft(varepsilon-1 · (1-γ)-2 · log3 A right) by using an action-sequentialization method.