Standard theoretical guarantees in reinforcement learning (RL) often rely on minimax analysis, which provides bounds for the "worst-case" environment. While mathematically robust, these bounds can be overly pessimistic. They treat every problem as if it were the most difficult possible configuration of states and rewards.
However, not all environments are created equal. In many real-world scenarios, the optimal action is significantly better than the alternatives. Recent research has shifted toward instance-dependent complexity, which seeks to understand how the specific structure of an environment—particularly the "gap" between optimal and sub-optimal choices—determines how much data an agent actually needs to learn.
The Sub-optimality Gap as a Signal
The core intuition behind this research direction is the sub-optimality gap ($\Delta$). This is the difference in value between the best action in a given state and the next-best alternative.
If the gap is large, the "signal" is clear: the agent can quickly distinguish the best policy from others even with noisy or limited observations. If the gap is tiny, the agent requires a massive amount of data to ensure it hasn't mistaken a near-optimal action for the truly optimal one. Taupin et al. argue that this gap is the fundamental constraint on the statistical difficulty of policy identification.
This shift in perspective changes the expected sample complexity of learning. For example, in offline reinforcement learning, Cui et al. demonstrate that the presence of a sub-optimality gap can improve sample complexity from a quadratic dependence on accuracy ($1/\epsilon^2$) to a linear one ($1/\epsilon$). Similarly, Nguyen-Tang et al. show that leveraging these gaps allows for faster convergence rates in offline settings than standard theory suggests.
Why Regret Minimization is Not Enough
A common goal in RL is regret minimization—maximizing cumulative reward while learning. However, Wagenmaker et al. prove that algorithms optimized for low regret are fundamentally suboptimal for pure exploration (finding the best policy).
Regret-minimizing algorithms are "optimistic"; they prefer to explore actions that might be good to avoid missing out on rewards. But to identify the best policy with high confidence, an agent often needs to spend time exploring "clearly sub-optimal" actions just to prove exactly how much worse they are. Wagenmaker et al. introduce the MOCA algorithm to address this, using aggressive, non-optimistic exploration to find optimal policies exponentially faster than regret-based methods in certain environments.
Scaling to High Dimensions
The challenge of the sub-optimality gap becomes more complex when agents cannot visit every state, such as in Linear MDPs where function approximation is required. In these high-dimensional spaces, the difficulty is not just the gap at a single state, but how that gap interacts with the feature geometry of the environment.
- Linear Convergence: Khodadadian et al. show that the Natural Policy Gradient (NPG) algorithm, which underlies popular methods like PPO, actually achieves geometric (linear) convergence speeds because the convergence rate is inherently tied to the distinctness of optimal choices.
- Logarithmic Regret: While standard linear RL theory predicts a square-root regret ($\sqrt{T}$), Zhou et al. prove that if a positive gap exists, agents can achieve logarithmic regret ($\log T$), bridging the gap between simple tabular models and complex function approximation.
- Experimental Design: To handle the "curse of dimensionality," Wagenmaker et al. introduced PEDEL, an algorithm that uses online experiment design to adapt to the specific difficulty of a linear environment. This allows the agent to outperform worst-case bounds by a factor proportional to the square of the feature dimensionality.
Adaptive Complexity and Oracle Inequalities
If an environment is "easy," the algorithm should know. This leads to the concept of instance-optimality, where the number of samples scales with the specific difficulty of the instance rather than a global bound.
Al Marjani et al. propose the COVGAME algorithm, which treats exploration as a game to meet specific sampling requirements, achieving near-optimal sample complexity by adapting to the "explorability" of the environment. In a similar vein, Zurek et al. introduce "oracle inequalities" for average-reward RL. These allow an algorithm to compete with the best policy-specific parameters (like the "span" of the value function) rather than a global worst-case parameter, enabling much faster learning when a "simple" near-optimal policy exists.
By focusing on the sub-optimality gap, these researchers have shown that RL is often much more efficient than minimax theory suggests. The difficulty of a task is not just a function of the state space size, but of how clearly the environment signals the right path.
Key Foundational Work
Best Policy Identification in Linear MDPs (2022) — contributed 2 concept elements to this direction.
Navigating to the Best Policy in Markov Decision Processes (2021) — contributed 1 concept elements to this direction.
Beyond No Regret: Instance-Dependent PAC Reinforcement Learning (2022) — contributed 1 concept elements to this direction.