Minimax Optimal Regret with Linear Function Approximation

17 concepts15 papers1 proposal

In reinforcement learning (RL), an agent seeks to maximize its cumulative reward by exploring an unknown environment. To evaluate an agent's efficiency, theorists measure its cumulative regret—the difference between the reward earned by an optimal policy and that earned by the agent.

For small, discrete environments, the fundamental limits of regret are well understood. In tabular settings, where states and actions can be individually enumerated, algorithms can achieve minimax optimal regret. This means their performance matches the information-theoretic lower bounds of the problem, ensuring no alternative algorithm can perform better in the worst-case scenario.

However, real-world environments possess massive or continuous state spaces. To make learning tractable, agents must use function approximation, representing the environment's structure via a manageable number of features (such as a linear combination). For years, a significant theoretical gap persisted: while tabular algorithms achieved optimal sample efficiency, algorithms utilizing linear function approximation suffered from sub-optimal regret bounds, typically losing a factor proportional to the feature dimension $d$ or the time horizon $H$.

A recent wave of research has successfully closed this gap. By replacing loose, worst-case uncertainty estimates with precise, variance-aware concentration mechanisms, researchers have demonstrated that agents can achieve minimax optimal regret even when scaling to high-dimensional linear environments.

The Statistical Gap: Hoeffding vs. Bernstein

To understand why early linear RL algorithms were sub-optimal, we must look at how agents handle uncertainty. To balance exploration and exploitation, optimistic algorithms add an exploration bonus to state-action values that have rarely been visited.

Early algorithms relied on Hoeffding's inequality to construct these bonuses. Hoeffding's inequality bounds the deviation of an empirical average from its true mean based solely on the maximum range of the random variables. In an MDP with a time horizon $H$, the value function can take values up to $H$. A Hoeffding-based bonus assumes that the variance of the next-state value function is always at its worst-case maximum ($H^2$) at every single step.

In reality, the true variance of the value function across next states is often much smaller. By overestimating uncertainty, Hoeffding-based algorithms over-explore sub-optimal paths, accumulating excess regret.

To achieve minimax optimality, algorithms must use Bernstein's inequality, which scales the exploration bonus according to the empirical variance of the random variables. In tabular RL, Azar et al. demonstrated that applying Bernstein concentration directly to the estimated value functions successfully eliminates loose dependencies on the horizon $H$, matching the lower bounds for finite-horizon environments. Similarly, Tossou et al. utilized empirical Bernstein inequalities to achieve optimal regret in tabular, infinite-horizon average-reward settings.

The Challenge of Function Approximation

While the transition from Hoeffding to Bernstein bounds is straightforward in tabular settings—where an agent can track the variance of each discrete state-action pair individually—it becomes highly complex under function approximation.

In a Linear MDP, the transition probabilities and reward functions are modeled as linear combinations of a $d$-dimensional feature mapping $\phi(s,a)$. Instead of counting visits to discrete states, the agent maintains a design matrix (or covariance matrix) $\Sigma = \sum \phi(s_t, a_t)\phi(s_t, a_t)^T$ to quantify its familiarity with different feature directions.

To achieve minimax optimality here, the agent cannot simply add a scalar variance bonus. It must perform variance-weighted ridge regression. When estimating the value function's parameters, the agent must discount highly unpredictable transitions and prioritize stable ones. The weighted covariance matrix takes the form:

$$\Sigma_{\text{weighted}} = \sum_{t} \frac{1}{\sigma_t^2} \phi(s_t, a_t)\phi(s_t, a_t)^T$$

where $\sigma_t^2$ is the conditional variance of the value function at the next state.

Implementing this framework requires overcoming two primary hurdles:

  1. Estimating the Variance: The agent does not know the true transition dynamics, so it cannot compute $\sigma_t^2$ directly. It must estimate the variance of the value function using a secondary linear regression model.
  2. Computational Feasibility: Iteratively solving variance-weighted regressions while maintaining upper confidence bounds can easily lead to exponential computational complexity if not designed carefully.

Closing the Gap in Linear Environments

Two distinct structural models dominate this line of research: Linear MDPs and Linear Mixture MDPs.

In Linear MDPs, Hu et al. introduced the LSVI-UCB⁺ algorithm, which incorporates a novel Bernstein-type exploration bonus into least-squares value iteration. By tightly bounding the total variance of the value function across a trajectory, the authors closed a long-standing $\sqrt{H}$ gap, proving that sample efficiency can scale optimally with a linear dependency on both the feature dimension and the horizon. To ensure this statistical optimality does not come at the cost of tractability, He et al. developed a polynomial-time algorithm that preserves these minimax optimal bounds, bridging the gap between theoretical limits and computational feasibility.

In Linear Mixture MDPs—where the transition kernel is a linear combination of known basis models—Zhou et al. achieved near-minimax optimality by constructing a local variance estimator. This approach allows the agent to exploit the underlying mixture structure, ensuring that large state spaces can be explored with the minimum possible loss in reward.

Beyond Fixed Horizons

The power of variance-aware estimation becomes even more pronounced when moving beyond standard finite-horizon environments into settings where the length of an episode is variable or infinite.

Stochastic Shortest Path (SSP) Problems

In SSP problems, an agent must reach a specific goal state while minimizing cumulative costs, meaning episode lengths are entirely dependent on the agent's policy. Traditional bounds in this setting often suffer from a dependency on the minimum possible cost or the maximum expected time to reach the goal. To resolve this, Di et al. introduced a recursive high-order moment variance estimator for linear mixture SSPs. By decoupling the regret bounds from scale-dependent parameters, the authors achieved minimax optimality across diverse cost scales.

Infinite-Horizon Average-Reward MDPs

In environments that never terminate, the agent's goal is to maximize its long-term steady-state average reward. Here, the standard notion of a time horizon $H$ is replaced by the span of the optimal bias function, which measures the long-term variation in rewards from different starting states.

Early work in this domain struggled with the restrictive assumption of "uniform mixing"—the idea that an agent can easily transition from any part of the environment to any other. Zhou et al. eliminated this requirement for linear environments, establishing that minimax optimal regret scaling with the square root of time is achievable without assuming the agent can never get stuck.

To improve computational efficiency in these perpetual environments, Hong et al. demonstrated that infinite-horizon linear MDPs can be efficiently solved in polynomial time by approximating them as discounted-reward MDPs. Meanwhile, Wei et al. provided baseline optimal regret bounds for long-term average reward tasks using linear models.

Alternative Paradigms and Generalizations

The core philosophy of minimizing regret via tight, information-theoretic bounds extends beyond online, optimistic linear models into non-stationary, offline, and general function approximation settings.

  • Non-Stationary Environments: When an environment's rewards and transitions change over time, an agent faces dynamic regret. Li et al. combined a "fixed-share" mechanism with an ensemble structure to achieve minimax optimal dynamic regret in linear mixture MDPs, matching the efficiency of stationary models relative to the degree of environmental change.
  • Offline Reinforcement Learning: In offline RL, the agent cannot explore; it must learn an optimal policy from a fixed, historical dataset. Yin et al. demonstrated that combining variance-aware regression with the principle of pessimism (penalizing poorly sampled feature directions) allows offline learning to reach near-minimax optimal sample complexity.
  • Information-Theoretic Exploration: Moving away from traditional optimism bonuses, Liu et al. introduced a complexity measure based on pure information gain. Their framework achieves optimal regret scaling in Bellman-complete environments, offering a unified approach to exploration that generalizes across different structural classes.
  • General Function Approximation: For environments that transcend linear structures, researchers have introduced broader complexity measures. Peng et al. leveraged low Bellman rank to achieve $\sqrt{n}$ cumulative regret using general function classes by reframing policy elimination as a contextual bandit problem. Similarly, He et al. introduced a unifying complexity measure to achieve near-optimal sublinear regret across a massive variety of infinite-horizon average-reward environments.

By shifting from worst-case error bounds to variance-aware estimation, modern reinforcement learning theory has proven that function approximation does not inherently require a sacrifice in statistical efficiency. Whether an environment is finite, infinite, stationary, or offline, tracking the intrinsic variance of value transitions allows agents to learn with mathematical optimality.

Key Foundational Work

Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities (2019) — contributed 1 concept elements to this direction.
Minimax Regret Bounds for Reinforcement Learning (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_minimax_optimal_regret_ca1f79f4,
  title = {minimax optimal regret},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimax-optimal-regret/rdr_ca1f79f4fe204c0b8c9226ae537189a9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_minimax_optimal_regret_ca1f79f4_v1,
  title = {minimax optimal regret},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimax-optimal-regret/rdr_ca1f79f4fe204c0b8c9226ae537189a9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake