- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies robust reinforcement learning with average rewards, where an agent learns from one trajectory of a nominal environment under worst-case transition uncertainty. The main finding is that learning difficulty depends on whether uncertainty can create new transitions:
- No new transitions: optimal policy regret scales as , under suitable structural conditions.
- New transitions allowed: the rate becomes when the nominal environment is communicating.
- Some relevant states cannot be revisited: linear regret can be unavoidable.
It also identifies three exact uncertainty thresholds governing communication and Bellman-equation solvability, and develops algorithms with matching lower bounds. These rates concern the long-run quality of announced policies, rather than accumulated realized rewards, and hold over families with bounded instance parameters.
Critical strengths
-
The setting considered in this paper is interesting. The problem of how the uncertainty threshold and the divergence function affect policy learning in the average-reward robust RL problem is underexplored.
-
This paper distinguishes three exact thresholds: preservation of a common communicating core, communication of every admissible model, and scalar Bellman solvability. Showing that Bellman solvability can persist beyond the communication thresholds is a useful theoretical insight; then provide a regret bound or imposibility results on different conditions.
Critical weaknesses
-
The mathematical expressions and symbols in the main text, as well as the appendix, are too much to read, which hinders a better understanding of the paper.
-
The matched rates concern the horizon exponent on families with bounded navigation times, local bias spans, minimum transition probabilities, and structural margins. Dependence on these quantities remains unmatched, which may still have potential effects on the upper bound.
Questions for authors
-
What is the meaning of a sublinear regret in equation (5), and how can it translate into suboptimality of the policy?
-
Is the proposed algorithms mainly informative theoretic? What is the computational complexity of the algorithm?
3 comments
I maintain my score.
Thank you for your follow-up. We have worked carefully to address each concern in our rebuttal. With the discussion period nearly over, we would value hearing which concerns, in your view, remain unresolved, where our responses remain insufficient, and what specific revisions would address those concerns.
Thank you for your review. We clarify the scope of the guarantees below.
W1. Exposition.
If accepted, we will add a small example of the three thresholds and a short explanation of how policy completion enters the regret proof. We will also explain earlier why transition creation can require costly exploration. These additions can improve accessibility while retaining the definitions needed for the results.
W2. What the matching rates claim.
The paper claims matching minimax exponents in T on parameter-bounded families. This scope is stated in the abstract and formalized by fixing S, A, and B in the minimax statement. The upper bounds separately display their instance dependence.
Matching every instance parameter would be a stronger result; it is not required to establish the stated horizon exponents. Even with those parameters controlled, transition creation changes the optimal exponent from 1/2 to 2/3 in the stated regimes. Related robust online work likewise characterizes power-law learnability while leaving gaps between its upper and lower bounds [1]. We will make the fixed-parameter scope more prominent alongside the rate statements.
Q1. Policy suboptimality.
The conversion follows directly from Eq. (5). For J uniform on 0,…,T−1 and independent of the nominal learning run,
=\frac{\mathbb E[\operatorname{Reg}_{\mathrm{pol}}(T)]}{T}.$$ Hence the two rates give expected robust shortfalls $\widetilde O(T^{-1/2})$ and $\widetilde O(T^{-1/3})$. Operationally, reveal $J$ only when it occurs and commit to $\pi_J$ from the current state $S_J$. The histories up to handover match the uninterrupted run, so this guarantee requires no return to a past state. It concerns the deployed policy's long-run gain; Section 5 distinguishes it from accumulated rewards under switching. For a prescribed training duration, Theorem 9 also gives $\widetilde O(m^{-1/2})$ robust suboptimality for Algorithm 1's plug-in policy after $m$ uniform-exploration steps, with probability at least $1-\alpha$ on fixed parameter-bounded families, subject to its support and accuracy conditions. Equivalently, $\widetilde O(\epsilon^{-2})$ nominal interactions suffice once those conditions hold, with logarithmic confidence dependence. **Q2. Computational complexity.** The guarantees are information-theoretic. Section 5 states that we do not claim polynomial running time. A direct $\mathsf{BellReady}$ implementation checks at most $3^S$ assignments to $I$, $J$, and their complement, with at most $SA$ row optimizations per assignment. Together with feasibility and support checks, this gives $O(SA3^S)$ row-optimization calls and additional graph checks. For our confidence sets, the row problems are linear programs. Their sizes depend on the accumulated confidence constraints. Optimistic robust planning over the confidence product is an additional step for which we establish no polynomial-time bound. This computational question is separate from the statistical minimax rates. We will add the operation count to the existing discussion. **Reference** 1. A. Appel and V. Kosoy. Regret Bounds for Robust Online Decision Making. COLT, 2025.