# Selecting the State-Representation in Reinforcement Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2013.

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

- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractions](https://mlsanity.com/paper/2112.13386/) (2021)
- [Scaling Laws for State Dynamics in Large Language Models](https://mlsanity.com/paper/2505.14892/) (2025)
- [Deformable Cluster Manipulation via Whole-Arm Policy Learning](https://mlsanity.com/paper/2507.17085/) (2025)

## Abstract (arXiv)

The problem of selecting the right state-representation in a reinforcement learning problem is considered. Several models (functions mapping past observations to a finite set) of the observations are given, and it is known that for at least one of these models the resulting state dynamics are indeed Markovian. Without knowing neither which of the models is the correct one, nor what are the probabilistic characteristics of the resulting MDP, it is required to obtain as much reward as the optimal policy for the correct model (or for the best of the correct models, if there are several). We propose an algorithm that achieves that, with a regret of order T^{2/3} where T is the horizon time.