acceptodds
Under review as a conference paper at ICLR 2027

Efficient Online Reinforcement Learning with All-Policy Linear -Realizability and Sparse Stochastic Transitions

Abstract

We study computationally efficient online reinforcement learning in potentially infinite state spaces. At each layer, every Markov policy's action-value function is linear in the same known -dimensional features, and each transition has at most possible successor states. Under these assumptions, we give a polynomial-time algorithm with high-probability regret for actions, horizon , and episodes. The algorithm discovers a finite set of noninitial states on which to concentrate learning, then combines a linear contextual bandit at the first layer with tabular learning on stored states and a fixed default policy elsewhere. The guarantee allows rewards in and arbitrary initial-state distributions. The algorithm uses only online episodes, without a simulator, resets to chosen states, or a policy-optimization oracle, and requires neither a linear transition model nor Bellman completeness.

Primary area:
learning theory
Keywords:
Theory of Reinforcement Learning, Policy Iteration, Linear Function Approximation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_9dRMOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies computationally efficient online reinforcement learning under all-policy linear Q-realizability and sparse stochastic transitions. The authors propose a polynomial-time algorithm that achieves high-probability O~(T)\widetilde{O}(\sqrt{T}) regret under exact realizability, with polynomial dependence on the feature dimension, horizon, number of actions, and transition support size. The result accommodates potentially infinite state spaces and arbitrary initial-state distributions, without requiring a simulator, a policy-optimization oracle, or Bellman completeness.

The main technical approach consists of discovering a finite set of relevant noninitial states, restricting subsequent learning to this set, and combining a linear contextual bandit at the initial layer with tabular reinforcement learning on the discovered states. The paper also extends the analysis to approximate realizability and approximately sparse transitions, and provides complementary lower bounds.

Critical strengths
  1. The main result establishes computationally efficient online learning under all-policy linear Q-realizability with sparse stochastic transitions. In particular, it extends the scope of efficient regret guarantees beyond the deterministic-transition setting considered in recent work. This is a worthwhile contribution to the literature on reinforcement learning with function approximation.

  2. The support-cover argument and the discovery procedure provide a useful way to reduce learning in a potentially infinite state space to a finite collection of relevant states. The combination of this reduction with contextual bandit learning at the initial layer is conceptually appealing.

Critical weaknesses

The main limitation is the strength of the structural assumptions. In particular, all-policy linear Q-realizability is considerably stronger than realizability of the optimal action-value function, and the sparse-transition assumption restricts the class of stochastic environments covered by the guarantee.

Questions for authors
  1. The regret guarantee includes a term linear in TT through χ=κ+Hυ/2\chi = \kappa + H\upsilon/2. Could the authors elaborate on the regimes in which the dependence on κ\kappa and υ\upsilon remains sufficiently small to yield sublinear regret? In particular, for approximately sparse transitions, is there a natural trade-off between KK and υ\upsilon that preserves a meaningful regret guarantee?

  2. Lemma 5.1 establishes a policy-independent support cover of size at most (2d−1)K(2d-1)K per layer, whereas the discovery procedure stores up to O~((H−1)d2K)\widetilde{O}((H-1)d^2K) states. Could the authors clarify which aspect of the online discovery procedure accounts for the additional factor of dd? Is this primarily a consequence of the multiple-matrix construction?

Reviewer_3hy4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates online reinforcement learning under the assumption that every Markov policy's action-value function lies in a linear space and that each transition has at most KK possible successor states. The authors establish a regret bound of O(dH2Amin⁡{A,d}KT)O(dH^2\sqrt{A\min\{A,d\}KT}), which improves previous results.

Critical strengths
  1. The regret bound improves upon the previous works listed in Table 1.
  2. The proposed algorithm has polynomial computational cost and proceeds without a simulator.
  3. An information-theoretic lower bound is established under the same assumptions, namely linear representation of the Q-function and sparse transitions.
Critical weaknesses
  1. The sparse-transition assumption appears to be imposed for the first time in this work. It would be expected to discuss whether this assumption is reasonable in practice. In addition, the regret has a linear dependency on vH4d2min⁡{d,A}TvH^4d^2\min\{d,A\}T, which is much larger than the first component dH2Amin⁡{A,d}KTdH^2\sqrt{A\min\{A,d\}KT} even if vv is a small constant. In particular, the regret of O(dH2Amin⁡{A,d}KT)O(dH^2\sqrt{A\min\{A,d\}KT}) can be achieved only when v≲1/(H2dT)v\lesssim 1/(H^2d\sqrt{T}), which is a relatively strong condition. The authors should discuss whether this condition can be satisfied in practice. If not, this assumption appears to be meaningless.

  2. Theorem 3.3 states that ``there is an online algorithm ...''. Does this refer to the algorithm proposed in Section 4? If so, it would be better to clarify this. If not, what is the performance of the proposed algorithm?

  3. The regret bound in Theorem 3.3 depends on the action space AA and the number of possible successor states KK, which reduces to the size of the state space when the sparse-transition assumption fails. In contrast, the previous regret bounds shown in Table 1 do not depend on AA. The improvement is achieved only when AKmin⁡{A,d}≤H2AK\min\{A,d\} \le H^2. This may fail when both the state and action spaces are large, or when the horizon is not long enough.

  4. Many existing works have studied the regret of linear MDPs, which share a similar assumption with this work. A minimax-optimal regret has been established for linear MDPs. This work makes a milder assumption, without assuming that the transition kernel is linear, and therefore achieves a worse bound. The authors may want to clarify what challenges are introduced into the analysis by removing this assumption. In particular, what is the technical novelty of this work compared to previous works on linear MDPs?

Questions for authors

see weakness

Reviewer_TdXLOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies computationally efficient online RL under all-policy linear qπq^π-realizability, an assumption weaker than linear MDPs that does not require Bellman completeness. It additionally assumes K-sparse stochastic transitions, which include deterministic dynamics as the case K=1K = 1. The key structural lemma is that each layer has an unknown set of O(dK)O(dK) states outside which actions barely matter under every continuation policy. Building on this, the algorithm first discovers a finite set of states and then runs tabular learning on that set, with a linear contextual bandit at the initial state. The result is a polynomial-time algorithm with regret O~(dH2√(A⋅min(A,d)⋅K⋅T))Õ(dH²√(A·min(A,d)·K·T)) under exact realizability. The paper also gives an Ω(H3/2√(dT))Ω(H^{3/2}√(dT)) lower bound.

Critical strengths
  1. The paper is the first to give a computationally efficient online algorithm under all-policy linear qπq^π-realizability with stochastic K-sparse transitions, a setting no prior work had addressed, and the contribution is technically solid.
  2. The paper complements the upper bound with lower bounds, showing the gap is only √(dH)√(dH) in the exact case and that a cost linear in kTkT is unavoidable.
Critical weaknesses
  1. Scope of the sparsity assumption. K-sparsity relaxes the deterministic dynamics assumed in prior efficient work, but it still excludes transitions with continuous noise, where υ = 1. Moreover, combined with Lemma 5.1, it reduces layers h ≥ 2 to a finite tabular problem, so the algorithm does not generalize across unseen non-initial states. It would help to discuss whether this is inherent to the approach.
  2. Incomplete comparison with [1]. In the deterministic case the result does not uniformly improve on [1]. The bound depends on A, which [1] does not. The analysis also requires i.i.d. initial states, whereas Ke et al. allow adversarial ones. Table 1 compares only the exact-realizability case and hides these differences.
  3. Lack of related citations. The paper stresses that it needs no simulator, but it does not discuss polynomial-time methods with local simulator access [2]. It also omits the hardness results under q*/v*-realizability [3, 4], which motivate the all-policy assumption.

[1] Frozen Policy Iteration: Computationally Efficient RL under Linear Realizability for Deterministic Dynamics

[1] Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs

[2] Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions

[3] Computational-Statistical Gaps in Reinforcement Learning

Questions for authors

See weakness.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.