Introduction
Reinforcement learning (RL) agents frequently operate in environments with massive or infinite state spaces, making it impossible to visit and evaluate every state. To navigate this, agents rely on function approximation to generalize experiences across states. While linear function approximation has enabled scaling beyond simple tabular RL, real-world dynamics are rarely perfectly linear. Generalized Linear Models (GLMs)—such as logistic regression—offer a more expressive alternative, but they introduce significant challenges for efficient exploration.
This paper introduces the first computationally and statistically efficient algorithm for RL using GLMs. By proposing a novel, relaxed expressivity assumption called "optimistic closure," the authors bridge the gap between simple linear models and more complex, non-linear function approximators, achieving provable sublinear regret.
The Challenge of Exploration
The primary hurdle in using GLMs for RL is ensuring the agent explores efficiently without getting trapped in suboptimal loops or requiring an impractical amount of time to learn. Previous theoretical guarantees for exploration relied heavily on restrictive "Linear MDP" assumptions, which often break down when non-linear link functions are introduced.
Methodology: LSVI-UCB for GLMs
To solve this, the authors adapt the Least-Squares Value Iteration with Upper Confidence Bound (LSVI-UCB) algorithm for GLMs. The approach is grounded in the "Optimism in the Face of Uncertainty" principle:
- Data Collection: The agent follows a greedy policy derived from its current model.
- Optimistic Update: During the Bellman backup (a standard RL update), the algorithm adds an optimism bonus. This forces the agent to overestimate the value of unfamiliar state-action pairs, naturally driving it to explore them.
- GLM Regression: Instead of standard linear regression, the algorithm solves a constrained least-squares problem utilizing a non-linear link function (e.g., a sigmoid function).
The "Optimistic Closure" Assumption
The mathematical foundation of this work is the new "optimistic closure" assumption. It posits that applying a Bellman update to a function from an enlarged class (the GLM plus the optimism bonus) results in a function that still resides within the original GLM class. Crucially, the authors prove this assumption is strictly weaker than the widely used Linear MDP assumption, allowing the algorithm to operate in a broader range of environments.
Key Theoretical Results
As a theoretical contribution, the paper focuses on rigorous mathematical guarantees rather than empirical benchmarks on datasets like Atari or MuJoCo.
The standout result is a cumulative regret bound of $\tilde{O}(H\sqrt{d^3T})$, where:
- $H$ is the time horizon.
- $d$ is the feature dimensionality.
- $T$ is the number of episodes.
Because the regret grows with the square root of $T$ ($\sqrt{T}$), the average regret per episode converges to zero over time, guaranteeing that the agent will eventually learn the optimal policy. Furthermore, these results successfully recover known bounds for tabular RL as a special case, demonstrating the algorithm's robustness across different scales.
Limitations and Future Directions
While GLMs strike a "sweet spot" between the expressivity of non-linear models and the tractability of linear ones, challenges remain:
- Closure in Practice: Although optimistic closure is a weaker assumption, it remains a significant structural requirement on the MDP's dynamics that may not hold perfectly in complex, real-world deep RL scenarios.
- Computational Scaling: The algorithm runs in polynomial time, but calculating the optimism bonus requires matrix inversions and Mahalanobis norms. These operations can become computationally expensive as feature dimensionality $d$ grows, highlighting the need for scalable approximations.
- Beyond GLMs: Extending these provably efficient exploration guarantees from GLMs to truly general function classes, such as deep neural networks, remains a major open frontier in reinforcement learning theory.
Summary updated