Abstract
In this paper, we study the problem of regret minimization for episodic Reinforcement Learning (RL) both in the model-free and the model-based setting. We focus on learning with general function classes and general model classes, and we derive results that scale with the eluder dimension of these classes. In contrast to the existing body of work that mainly establishes instance-independent regret guarantees, we focus on the instance-dependent setting and show that the regret scales logarithmically with the horizon $T$, provided that there is a gap between the best and the second best action in every state. In addition, we show that such a logarithmic regret bound is realizable by algorithms with $O(\log T)$ switching cost (also known as adaptivity complexity). In other words, these algorithms rarely switch their policy during the course of their execution. Finally, we complement our results with lower bounds which show that even in the tabular setting, we cannot hope for regret guarantees lower than $o(\log T)$.
Introduction
In theoretical Reinforcement Learning (RL), the standard metric for performance is regret—the cumulative difference between the rewards an optimal agent would receive and those collected by the learning agent. Historically, most theoretical guarantees have focused on "worst-case" or instance-independent scenarios, where regret typically grows at a rate of $O(\sqrt{T})$, where $T$ is the number of interactions. While these bounds are robust, they are often overly pessimistic for real-world environments that possess benign structural properties.
Furthermore, traditional RL algorithms often assume that the agent can update its policy after every single interaction. However, in many practical applications—such as clinical trials, industrial control, or recommendation systems—frequent policy changes are expensive, risky, or logistically impossible. This constraint is known as adaptivity complexity or switching cost. This paper addresses a fundamental question: Can we achieve the "gold standard" of efficiency (logarithmic regret) while maintaining high stability (logarithmic policy switches) in complex environments requiring general function approximation?
Problem Formulation and the Power of the Gap
The authors shift the focus to the instance-dependent setting. The critical assumption here is the existence of a sub-optimality gap ($\text{gap}_{\min} > 0$). This gap represents the minimum difference in value between the optimal action and the next-best action in any given state.
When such a gap exists, an agent does not need to explore indefinitely. Once the agent has collected enough data to statistically distinguish the optimal action from sub-optimal ones, the regret stops growing at a $\sqrt{T}$ rate and transitions to a logarithmic growth rate. This represents an exponential improvement in learning efficiency.
Methodology
The paper proposes a unified framework applicable to both model-free RL (directly estimating action values) and model-based RL (learning the underlying transition dynamics). The approach is built on several key pillars:
1. Low Switching Cost Value Iteration
The core algorithm utilizes a "lazy" update mechanism. Instead of updating the policy every episode, it employs an Online Sub-sampling routine. The agent only triggers a policy update if the newly acquired data is "significant" enough to meaningfully change the agent's confidence in its current model. This sensitivity-based filtering ensures that the agent ignores redundant interactions, keeping the switching cost low.
2. General Function Approximation and Eluder Dimension
To move beyond simple tabular or linear models, the authors utilize general function classes. To quantify the complexity of these classes, they employ the Eluder Dimension ($d_{\mathcal{F}}$). This metric captures the number of "independent" queries required to learn a function within a class, providing a powerful tool for analyzing non-linear approximation in RL.
3. Exploration and Analysis
The algorithm combines Least-Squares Regression to estimate Q-functions with an Upper Confidence Bound (UCB) bonus to drive exploration in uncertain regions of the state-action space. For the mathematical proof, the authors use a "peeling" technique, decomposing total regret into intervals based on the size of the sub-optimality gap. This allows them to strictly bound the number of times a sub-optimal action is selected.
Key Results
The theoretical contributions of this work are three-fold:
- Logarithmic Regret: The authors establish a regret bound of $O(\text{poly}(\log T, H, d_{\mathcal{F}}) / \text{gap}_{\min})$. This confirms that in the presence of a gap, regret grows only logarithmically with time, even with general function approximation.
- Logarithmic Switching: The number of policy updates is bounded by $O(\text{poly}(\log T, H, d_{\mathcal{F}}))$. This implies that over millions of episodes, the agent may only need to change its strategy a handful of times, making the algorithm highly suitable for real-world deployment.
- Near-Optimal Lower Bounds: The authors provide a lower bound proof showing that even in the simplest tabular settings, regret cannot be lower than $o(\log T)$. This confirms that their achieved logarithmic regret is near-optimal.
Limitations and Future Work
While the paper marks a significant advancement, several areas remain for future exploration:
- Planning Horizon ($H$): The current dependence on the planning horizon $H$ is polynomial. Establishing the optimal dependence on $H$ remains an open theoretical challenge.
- Gap Sensitivity: The logarithmic regret is inversely proportional to the sub-optimality gap. In environments where the gap is infinitesimally small, the regret bound may "explode," effectively reverting to the $O(\sqrt{T})$ regime.
- Computational Complexity: The work focuses on sample complexity and switching costs. However, the computational burden of solving least-squares optimization for complex, non-linear function classes at each update step remains a practical hurdle.
Summary updated