Research map / Reinforcement learning / MDPs and planning
Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first computationally efficient online RL algorithm for linear Bellman complete MDPs with deterministic dynamics (large action spaces, stochastic rewards and initial states), using null-space Gaussian noise randomization for optimism and a span argument, with a random-walk convex feasibility oracle.
Problem
Online RL under linear Bellman completeness is statistically tractable but no computationally efficient algorithm was known, especially with large action spaces, random initial states and random rewards.
Approach
Randomized least-squares value iteration that injects Gaussian noise only into the null space of the historical feature covariance, so that under deterministic dynamics value estimates are exact within the data span; a span argument bounds rounds where trajectories leave the span (at most dH times), avoiding exponential parameter blow-up without truncation.
Key results
- Regret bound of order d^{5/2}H^{5/2} + d^2 H^{3/2} sqrt(T) under exact squared-loss oracle, independent of number of actions.
- Sample complexity bound T >= Omega(d^4 H^3 / eps^2) for epsilon-optimal policy.
- Random-walk-based convex feasibility oracle runs in O(d^7 log(R/(delta r))) time with O(d log(R/(delta r))) separation-oracle calls.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| inject value-function noise only in the null space of the historical data | Null Space Randomization · Linear Bellman completeness with deterministic dynamics | regret: \~O ( d^{5/2} H^{5/2} + d^2 H^{3/2} \sqrt{T}) | Helped |
| use a known reward function | Null Space Randomization · Linear Bellman completeness with deterministic dynamics | regret: \~O(dH^2) | Helped |
| use an approximate squared loss minimization oracle | Null Space Randomization · Linear Bellman completeness with deterministic dynamics | regret: additional term: \varepsilon_1\gamma \big(d H^2 + d^{3/2} H \sqrt{T} \big) | Hurt |
| allow εB-inherent linear Bellman error | Null Space Randomization · Low inherent linear Bellman error, deterministic dynamics | regret: \sqrt{\epsB} \big( d^2 H^{5/2} \sqrt{T} + d^{3/2} H^{3/2}T \big) + \epsB \gamma \big(d H^2 \sqrt{T} + d^{3/2} H T \big) | Hurt |
| use a span argument to bound rounds outside the historical data span | Null Space Randomization · Linear Bellman completeness with deterministic dynamics | number of out-of-span rounds: \leq d H | Helped |
Surprising findings
- Parameter norms can grow exponentially with horizon under linear Bellman completeness, so prior norm-bounded or truncation-based RLSVI analyses fail.
- Bellman backup can be l2-expansive even in tabular MDPs, showing non-expansiveness assumptions are too strong.
Limitations
- Requires deterministic transition dynamics; extension to stochastic dynamics is open.
- Requires a linear optimization oracle over features (argmax) and a bounded-set assumption with parameter R that may be exponential in d or H.
Experimental setup
Metrics: regret sample complexity
Baselines: LSVI-UCB RLSVI few-action linear Bellman complete algorithm
Builds on: RLSVI LSVI-UCB random-walk convex feasibility (Bertsimas-Vempala style) D-optimal design
Closest papers by meaning
- Learning Near Optimal Policies with Low Inherent Bellman Error (ICML 2020 · similarity 0.90)
- Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework (NeurIPS 2026 · similarity 0.89)
- Gradual Transition from Bellman Optimality Operator to Bellman Operator in Online Reinforcement Learning (ICML 2025 · similarity 0.88)
- Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- Enhancing Value Function Estimation through First-Order State-Action Dynamics in Offline Reinforcement Learning (ICML 2024 · similarity 0.88)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.