- 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 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
-
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.
-
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
-
The regret guarantee includes a term linear in through . Could the authors elaborate on the regimes in which the dependence on and remains sufficiently small to yield sublinear regret? In particular, for approximately sparse transitions, is there a natural trade-off between and that preserves a meaningful regret guarantee?
-
Lemma 5.1 establishes a policy-independent support cover of size at most per layer, whereas the discovery procedure stores up to states. Could the authors clarify which aspect of the online discovery procedure accounts for the additional factor of ? Is this primarily a consequence of the multiple-matrix construction?