Abstract
We consider the problem of online reinforcement learning when several state representations (mapping histories to a discrete state space) are available to the learning agent. At least one of these representations is assumed to induce a Markov decision process (MDP), and the performance of the agent is measured in terms of cumulative regret against the optimal policy giving the highest average reward in this MDP representation. We propose an algorithm (UCB-MS) with $O(\sqrt{T})$ regret in any communicating Markov decision process. The regret bound shows that UCB-MS automatically adapts to the Markov model. This improves over the currently known best results in the literature that gave regret bounds of order $O(T^{2/3})$.
Introduction
In Reinforcement Learning (RL), the "state" is a fundamental concept—a compact summary of history that ensures the environment is Markovian, meaning the future depends only on the current state and not the sequence of events that preceded it. In practice, however, agents often deal with high-dimensional observations (such as raw sensor data or images) rather than clean state spaces. Designing a mapping from these observations to a proper state space is a significant challenge.
This paper investigates the representation selection problem. In this setting, an agent is provided with a set of candidate representations (mappings from history to discrete states). While the agent does not know which representation is correct, at least one is guaranteed to be Markovian. The objective is to interact with the environment to identify an effective representation while simultaneously maximizing cumulative rewards. The performance is measured by cumulative regret: the difference between the total reward the agent actually collected and the reward it would have collected had it known the optimal policy for the best Markovian representation from the start.
Bridging the Theoretical Gap
Prior to this work, the theoretical landscape for representation selection was limited. The best-known valid regret bound was $O(T^{2/3})$, achieved by algorithms like BLB. While other attempts (such as the OMS algorithm) claimed to reach the "gold standard" of $O(\sqrt{T})$ regret, their proofs were found to be mathematically flawed. This paper introduces UCB-Model Selection (UCB-MS), providing the first sound proof for an $O(\sqrt{T})$ regret bound in this context. This improvement is significant: as $T$ increases, an $O(\sqrt{T})$ algorithm ensures that the average regret per step vanishes much faster than an $O(T^{2/3})$ algorithm, leading to vastly more efficient long-term learning.
The UCB-MS Algorithm
UCB-MS builds upon the classic UCRL2 (Upper Confidence Reinforcement Learning) framework, extending it with a meta-layer designed for model selection. The algorithm operates through three primary mechanisms:
- Optimism in the Face of Uncertainty: At the beginning of each episode, the agent evaluates all available representations. For each candidate, it calculates the "optimistic" average reward possible. The agent then selects the representation that promises the highest potential reward.
- Performance-Based Elimination (The Sanity Check): As the agent interacts with the environment using the chosen representation, it monitors its actual performance. If the collected rewards fall significantly below the theoretical performance of a true Markovian model (based on known UCRL2 regret bounds), the agent concludes that the representation is likely non-Markovian and eliminates it from the candidate set.
- Diameter Adaptation via Doubling: Standard RL algorithms often require prior knowledge of the environment's "diameter" (the time required to transition between any two states). UCB-MS circumvents this by using a doubling scheme. It starts with a small estimate for the diameter and doubles it whenever all current models are eliminated, restarting the process. This approach avoids the exponential regret penalties seen in previous selection methods.
Key Insights
"Happy to be Wrong"
A core conceptual insight of UCB-MS is that the agent does not strictly need to find the "true" Markovian representation. If a non-Markovian representation happens to provide rewards equivalent to or better than a Markovian one, the agent can continue using it without penalty. The algorithm only discards models that "under-perform" relative to their optimistic promises.
Effective State Space ($S_\Phi$)
To handle scenarios where candidate representations might be related or nested (such as hierarchies), the authors introduce the concept of an effective state space. This ensures that the agent does not pay a complexity penalty for every single state in every model. Instead, the regret scales with the total number of unique states across the combined representations ($S_\Sigma$), allowing for more efficient learning when models share structure.
Results and Limitations
The paper proves that UCB-MS achieves a regret bound of $O(\sqrt{S_{max} S_\Sigma A T \log(T/\delta)})$. This result confirms that the algorithm automatically adapts to the best available Markovian model without prior knowledge. Furthermore, the doubling scheme for the unknown diameter $D$ is shown to be highly efficient, adding only logarithmic factors to the regret.
Despite these advances, some limitations remain:
- Finite Model Sets: The current theory applies to a finite set of candidate representations. Extending these guarantees to infinite or continuous classes (such as neural network architectures) is an open challenge.
- Perfect Markov Assumption: The proof assumes at least one model is perfectly Markovian. In real-world applications, representations are often only "approximately" Markovian. While the authors suggest the framework could be adapted for approximate models, formal proofs for that setting are left for future research.
Summary updated