Abstract
We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $\tilde O(d\sqrt{H^3K})$, where $d$ is the dimension of the feature mapping, $H$ is the planning horizon, and $K$ is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the optimal value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
Introduction
Reinforcement Learning (RL) faces a fundamental trade-off between theoretical optimality and practical scalability. While tabular RL—where states and actions are discrete—is well-understood, scaling to large or continuous state spaces requires function approximation. The Linear Markov Decision Process (Linear MDP) is a cornerstone framework for studying this. In a Linear MDP, transition probabilities and rewards are linear functions of a $d$-dimensional feature mapping.
Despite its importance, a gap persisted between the regret of existing algorithms and the theoretical minimax lower bound. Regret measures the difference between the total reward an optimal agent would receive and what the learning algorithm actually collects. For Linear MDPs, the theoretical lower bound is $\Omega(d\sqrt{H^3K})$. Previous state-of-the-art methods, such as LSVI-UCB, achieved $\tilde{O}(\sqrt{d^3H^4K})$, leaving a gap of $\sqrt{d}$ and $\sqrt{H}$. This paper introduces LSVI-UCB++, the first computationally efficient algorithm to close this gap.
Methodology
LSVI-UCB++ builds upon the Least-Squares Value Iteration (LSVI) framework with three key innovations designed to tighten the regret bound:
- Weighted Ridge Regression: Instead of standard regression, the algorithm weights data points by the inverse of their estimated variance. This variance-aware approach, while common in tabular RL, is significantly more complex to implement in the linear setting.
- Novel Variance Estimator: The "secret sauce" of the algorithm is a variance estimator that directly targets the optimal value function ($V^*$). By decomposing the current estimate into $V^*$ and a sub-optimality gap, the authors achieve much tighter confidence intervals than previous methods that relied on broad covering numbers.
- Rare-Switching Policy: To manage computational complexity and control the complexity of the estimated value function class, the algorithm does not update its policy every episode. Instead, it updates only when the information gathered (represented by the determinant of the covariance matrix) doubles. This happens only $O(dH \log K)$ times.
Results and Analysis
The primary contribution of this work is the achievement of a regret bound of $\tilde{O}(d\sqrt{H^3K})$, which matches the theoretical lower bound up to logarithmic factors.
As shown in the table above, LSVI-UCB++ successfully removes the extra factors of $d$ and $H$ that were present in earlier work. Beyond regret optimality, the rare-switching strategy yields a significant computational speedup, reducing total complexity to $O(d^4H^3|A|K)$. This makes the algorithm a factor of $K$ more efficient than non-switching approaches.
Conclusion
LSVI-UCB++ provides a definitive answer to the problem of minimax optimal RL in Linear MDPs. The success of the algorithm hinges on the decomposition of the value function and the enforcement of monotonicity in estimators, bypassing the limitations of standard covering number arguments. While the current model assumes a known linear feature mapping, the principles of variance-aware estimation and rare-switching provide a robust roadmap for future research into general nonlinear function approximation and horizon-free RL.
Summary updated