Average-Reward Policy Identification from a Single Continuing Trajectory
This paper studies whether learning an epsilon-optimal average-reward policy from a single continuing trajectory must pay an extra navigation cost compared with generative access. It develops an adaptive algorithm that learns a low-cost sampling allocation via inverse-count exploration and converts nonuniform samples into an all-state policy certificate using a transient-corrected quantile bound. For broad model classes and sufficiently high accuracy, it proves that the worst-case sample complexity matches the generative lower bound up to logarithmic factors, removing the extra diameter factor that plagued prior continuing-access bounds.
The paper delivers a strong theoretical advance: under stated conditions, it is the first to show that average-reward policy identification from a single trajectory can match the generative-model worst-case rate $\widetilde{\Theta}(SA\overline{D}/\epsilon^2)$. The analysis is sophisticated, linking adaptive trajectory flow to balanced-flow collection cost and using an auxiliary-bias cancellation to keep transient errors at order $M^{-1}$ rather than $M^{-1/2}$. Nevertheless, the matching regime is restricted (e.g., $\epsilon \leq 1/32$ and bounded support or high accuracy), and the algorithm is extremely complex, with no published implementation or empirical baseline comparison.
The most compelling contribution is the matching upper and lower bounds in Corollary 2, where continuing and generative access share complexity $\widetilde{\Theta}(SA\overline{D}/\epsilon^2)$ for two-successor classes and unrestricted support at high accuracy. The technical apparatus is sound: the time-uniform trajectory flow bound (Proposition 5) shows that empirical inverse-count allocations admit low balanced-flow cost even before stationarity, and the nonuniform estimation argument uses an auxiliary bias truncation so that statistical error scales as $M^{-1/2}$ while transient imbalance scales as $M^{-1}$. Relative to prior art, the precision term improves from $\widetilde{O}(SAD^2/\epsilon^2)$ to $\widetilde{O}(SAD/\epsilon^2)$.
The claimed matching is limited to specific regimes: for unrestricted support, it holds only when $\epsilon^2 \min\{S,\overline{D}\} \leq 1$, and the paper explicitly notes that "access-model matching remains open" outside this condition (Section 3.2). The lower bound is classwise and uses a shared reward table, so it does not preclude instance-dependent gaps. The upper bound also retains a lower-order $SAD/\epsilon$ transient term and a startup cost $\widetilde{O}(A_{\rm mix})$ that can dominate when accuracy is coarse. Furthermore, the algorithm is a highly intricate double-loop schedule with dyadic guesses for pilot length and mass, nested confidence sets, and rounded Bellman backups; as presented, it is essentially unimplementable without major simplification, and there is no empirical validation of the full adaptive algorithm.
The paper fairly positions its bound against prior continuing-access results: Online-DFE (Tuynman et al., 2024) suffers a $D^2$ precision penalty, while a naive generative-planner plus collector composition retains a diameter factor in both startup and precision terms (Table 1). The new bound replaces the precision term with $SA(B_*+1)/\epsilon^2 + SAD/\epsilon$, which is never worse and can be much better when $B_* \ll D$. The comparison to behavior-policy methods such as SAVIC+ (Lee et al., 2026) is also transparent: SAVIC+ relies on coverage parameters of the behavior policy, which are unrelated to the controlled diameter and do not yield worst-case matching with generative access. The lower-bound construction in Section 6 is clean, showing that even generative samples carry only $O(\epsilon^2/\overline{D})$ information per query on the hard family, so the diameter dependence is statistical rather than purely navigational.
A full independent reproduction would be extremely difficult. No code repository or pseudocode implementation is provided. Hyperparameters are not fixed constants but data-dependent schedules with dyadic caps $U_j = 2^j$, event allowances $\eta_j = \delta/[64(j+1)^4]$, and lexicographic enumeration over pilot and mass pairs, all requiring careful book-keeping of nested confidence regions and scalar buffer restarts (Appendix B.4). While the paper proves polynomial bit work on the success event (Theorem 1; Appendix E), the constants are astronomical and the algorithm relies on exact fixed-point computations and dyadic discount searches that would need substantial engineering to realize. Appendix H contains only a numerical illustration of the statistical certificate under uniform allocation, not an end-to-end simulation of the adaptive method.
In reinforcement learning, an agent must explore an unknown environment to learn how to make good decisions. Unlike methods that can freely sample any state--action pair, an agent learning from a single trajectory must spend additional time navigating between states. It is therefore natural to expect that learning from a single trajectory requires more experience. In this paper, we show that this additional cost is not always necessary. For average-reward reinforcement learning, we develop an algorithm that learns where to collect information while ensuring that the required samples can be obtained efficiently. We establish an upper bound on the number of interactions needed to identify a near-optimal policy. Furthermore, we prove a matching information theoretic lower bound, showing that, for a broad class of environments and at sufficiently high accuracy, learning from a single trajectory is no harder in the worst case than learning with unrestricted access to state action samples. Our results reveal that the additional complexity cost of navigation can be avoided by adapting information gathering requirements to how the environment provides information.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.