acceptodds
Under review as a conference paper at ICLR 2027

Limits of Online Distributionally Robust Average-Reward Reinforcement Learning

Abstract

We establish matching minimax horizon exponents for single-trajectory robust average-reward learning on tabular MDP families with bounded parameters. The learner observes transitions from an unknown nominal model , while stationary policies are evaluated by their worst-case average reward over a rectangular -divergence ball of radius . The deletion cost measures the minimum divergence needed to remove a transition, while the asymptotic slope determines whether new transitions can be created. These yield three exact radii , characterizing, respectively, a common transition set guaranteeing weak communication, weak communication of every plausible model, and solvability of the robust Bellman equation with a state-independent gain for every bounded reward. For suitable fixed state and action counts and parameter bounds, minimax policy regret is when transition creation is impossible and , even with nominal transient states. With creation and , the rate is for communicating nominal MDPs, while linear regret can be unavoidable otherwise. At , every transition model is admissible and zero regret is achievable. A Bellman completion construction establishes the square-root upper bound beyond both communication thresholds.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, robust reinforcement learning, Markov decision processes, average-reward reinforcement learning, distributionally robust optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_V9DxOpenReview ↗
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 Θ~(T)\widetilde{\Theta}(\sqrt T), under suitable structural conditions.
  • New transitions allowed: the rate becomes Θ~(T2/3)\widetilde{\Theta}(T^{2/3}) 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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. What is the meaning of a sublinear regret in equation (5), and how can it translate into suboptimality of the policy?

  2. Is the proposed algorithms mainly informative theoretic? What is the computational complexity of the algorithm?

3 comments

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 TT on parameter-bounded families. This scope is stated in the abstract and formalized by fixing SS, AA, and BB 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/21/2 to 2/32/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 JJ uniform on 0,…,T−1\\{0,\ldots,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.

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.

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

This paper studies online distributionally robust average-reward reinforcement learning from a single nominal trajectory, with known rewards and state-action rectangular f-divergence uncertainty. It distinguishes three thresholds dominating a common robust support core, communication of individual ambiguity kernels, and scalar robust Bellman solvability. On parameter-bounded families, it establishes matching policy-regret exponents: T1/2T^{1/2} without transition creation under the Bellman condition, and T2/3T^{2/3} with creation under nominal communication and below saturation. It also proves a linear lower bound without nominal communication in the creation setting and zero regret when the ambiguity sets are full simplices.

Critical strengths
  1. The structural characterization is informative. Theorems 1-3 distinguish conditions that are easily conflated. In particular, losing weak communication in an ambiguity kernel need not destroy scalar robust Bellman solvability. The deletion-cost characterization and strict-separation examples clarify these distinctions.

  2. The rate results involve substantive technical ideas. Theorem 14 relates information acquisition to costly revealing actions, explaining the T^(2/3) lower bound. For the square-root upper bound, Proposition 8 completes greedy policies so that adversarial recurrent classes lie within a selected nominal recurrent class. This supports the occupation comparison without assuming every greedy policy is unichain.

Critical weaknesses

My main concern is the operational interpretation of policy regret in Equation (5). Each announced policy is evaluated as if followed indefinitely, although only one action may be executed before switching policies. Thus zero policy regret can coexist with linear cumulative-reward regret: in a communicating two-state MDP with singleton ambiguity sets, every announced policy reaches a reward-one state almost surely when held fixed, while successively shrinking its transition probability leaves the executed process in a reward-zero state with positive probability forever. Section 5 distinguishes these objectives, so this is a limitation of interpretation rather than a contradiction of the theorem.

Questions for authors
  1. What deployment setting motivates Equation (5), given that small policy regret need not control executed rewards?

  2. Can the existing readiness conditions be consolidated into a sufficient horizon condition for Corollary 2, with a KL or TV example showing the dependence on structural margins?

  3. Can the main text explain how Proposition 8 preserves greedy actions on the selected class, excludes adversarial recurrence outside it, and enables Theorem 13? I think add a proof sketch would significantly increase the readability.

3 comments

Thank you for the careful reading and the specific questions.

W1/Q1. Deployment interpretation.

Your example is consistent with the distinction stated in Section 5. Eq. (5) evaluates the robust long-run gain of each announced stationary policy; it does not claim to control accumulated rewards under repeated switching.

The intended deployment setting is nominal training followed by commitment to a stationary policy under potentially different dynamics. Let JJ be uniform on 0,…,T−1\\{0,\ldots,T-1\\}, independent of the learning run and revealed only at handover. Run the original horizon-TT learner until JJ, then commit to πJ\pi_J from the current state SJS_J. The nominal histories before handover have the same distributions as in the uninterrupted run, giving

=\frac{\mathbb E[\operatorname{Reg}_{\mathrm{pol}}(T)]}{T}.$$ Sublinear policy regret therefore controls expected robust deployment suboptimality at this handover. No return to a previous state is needed. Theorem 9 also gives a fixed-policy guarantee after a prescribed exploration duration, under its support and accuracy conditions. We will place the handover interpretation alongside Eq. (5). **Q2. Sufficient readiness horizons.** The existing conditions can be consolidated as $$n_\star(P,\alpha):=n_{\mathrm{supp}}(P,\alpha) \vee\min\left\\{n\ge1:2\beta_{\alpha/3}(n)\le\frac{\Delta_{\mathrm{bell}}(P_R)}{16}\right\\}.$$ Under the respective structural assumptions, $m\ge\mathfrak t_P(n_\star(P,\alpha),\alpha)$ suffices for support recovery and the Bellman-completion certificate. It also suffices for explore-then-commit, since $\bar\epsilon_{\mathrm{face}}(P_R)\ge\Delta_{\mathrm{bell}}(P_R)/16$. With $\alpha=1/T$, let $$M:=D_0(P)d_RA\left[p_{\min,R}^{-1}+S\Delta_{\mathrm{bell}}(P_R)^{-2}\right].$$ The sufficient exploration budget is $\widetilde O(M)$. The two exploration schedules therefore give sufficient total-horizon thresholds $$T_{0,\mathrm{BC}}=\widetilde O(M^2), \qquad T_{0,\mathrm{ETC}}=\widetilde O(M^{3/2}).$$ Logarithms include the dependence on $T$ through $\alpha=1/T$. On the families in Corollary 2, $D_0(P),p_{\min,R}^{-1}\le B$, $d_R\le S$, and $\Delta_{\mathrm{bell}}(P_R)^{-1}=O_{f,\delta}(B)$, so $M=O_{f,\delta}(S^2AB^3)$. This supplies a uniform sufficient horizon for that corollary. For KL, $\theta_f(q)=-\log(1-q)$ and $q_\star=1-e^{-\delta}$. If $m_{\mathrm{bell}}(P_R)=\eta\le\min\\{1,p_{\min,R}\\}$, then $\Delta_{\mathrm{bell}}(P_R)=\eta$. Holding navigation and minimum positive transition probabilities fixed, the sufficient per-row threshold is $\widetilde O(\eta^{-2})$ and the Bellman-completion readiness horizon is $\widetilde O(\eta^{-4})$. We will include this consolidated condition and example in the final version. **Q3. How completion enters the regret proof.** Proposition 8 preserves the greedy actions on the selected nominal recurrent class $R$. The Bellman completion in Proposition 9 extends this construction beyond the common-core threshold. For a remaining set $X$ outside $R$, it chooses a row whose outgoing mass exceeds $q_\star$ uniformly over the confidence product. The adversary cannot delete all those exits. Removing the chosen state and repeating rules out every adversarial recurrent class outside $R$ by the earliest-removal argument. No creation keeps $R$ closed. On every adversarial recurrent class within $R$, greedy equality and stationarity cancel the bias terms; the row-wise minimizing kernel gives the reverse bound. Thus completion preserves the selected center's robust gain. Under the nominal model the completed policy has the unique recurrent class $R$, enabling the stationary-weight comparison through $C_{\mathrm{occ}}$. Theorem 13 combines this comparison with the finite-horizon occupation bound and episode doubling to obtain $\widetilde O(\sqrt T)$. If accepted, we will add this proof sketch to the main text.

Thank you for your response. I appreciate the authors' effort; I maintain my positive score.

Thank you for your feedback and continued support. With the discussion period nearly over, we would welcome any remaining concerns or suggestions after our rebuttal, particularly your perspective on specific revisions that would address them and further improve the paper.

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

This paper treats the problem of learning in robust MDPs. The set of allowed transition kernels is a rectangle.
The key highlights of this work, which set it apart from existing ones, are as follows:

Firstly, the learning happens on a single Markovian trajectory, rather than using a generative model for data collection. The sampling policy changes in an online manner. It seems to me that one key aspect of this work is that it explicitly shows which problemsare "hard" and which ones are easy.

However, if the uncertainty set is only going to change the probabilities associated with different types of transitions, the learning problem is relatively easier, and regret grows as T^.5.

If the uncertainty set is allowed to create MDP transitions of new kind, then the leaning problem becomes harder, and regret grows as T^2/3. Furthermore, if the states could be transient (so that there is a possibility that the agent never returns to some states), then even linear regret (T) is possible.

Critical strengths

This paper treats the problem of learning in robust MDPs. The set of allowed transition kernels is a rectangle.
The key highlights of this work, which set it apart from existing ones, are as follows:

Firstly, the learning happens on a single Markovian trajectory, rather than using a generative model for data collection. The sampling policy changes in an online manner. It seems to me that one key aspect of this work is that it explicitly shows which problemsare "hard" and which ones are easy. If the uncertainty set is allowed to create MDP transitions of new kind, then the leaning problem becomes harder, and regret grows as T^2/3. However, if the uncertainty set is only going to change the probabilities associated with different types of transitions, the learning problem is relatively easier, and regret grows as T^.5.

Critical weaknesses
  1. There are some issues in the current proof, that I have posed as questions to authors below.

  2. I find it hard to digest the part of formulation concerned with "uncertainty sets". Requiring them to be rectangular is too restrictive.

  3. The paper is hard to read, and begins with very abstract material. It will be better to start with less mathematical formulation. Just by reading the introduction or related works section, we should be able to pinpoint the exact contribution. Currently this is not the case. As an example, the firse bullet in contributions reads:

"We identify three sharp radii δ∗f (P) ≤ δ† f (P) ≤ δbell f (P) governing weak communication.." Now you do not expect a reader to know what is meant by "weak communication" at this initial stage of the paper. Make the first 4 pages less technical and accessible to someone who is not too much familiar with thetechniques of this paper.

  1. I am not sure whether the notion of regret here makes sense. A "convergence" rate/ sample complexity seems more natural. For example, after T steps of interaction with environment, give me a policy such that the worst-case performance (with an adversarial nature choosing the MDP on which we will evaluate the performace) is within epsiln of the "optimal" worst-case performance.
Questions for authors

First two concerns are of technical nature. Beyond that, its more about presentation.

  1. Algorithm 2: can you prove the existence of maximizers in step 7? If not, then I am afraid that the algorithm may not be well-defined.

  2. Lines 890-898: can you prove the existence of an optimistic eigenpair? There could be counter examples when such an existence is not guaranteed.

  3. Can you try to make the main paper less terse and abstract? Though it contains material that seems publishable, but the main paper is hard to follow. Technical details should be delegated to appendix.

  4. Can you draw a table showing what is lacking in previous existing works, and how does your work go beyond that. In the absence of an explicit comparison, its hard to judge the novelty of current work.

  5. I am not sure whether the notion of regret here makes sense. A "convergence" rate/sample complexity seems more natural. For example, (in a probabilistic sense, e.g. with high probability) after T steps of interaction with environment, give me a policy such that the worst-case performance (with an adversarial nature choosing the MDP on which we will evaluate the performace) is within epsilon of the "optimal" worst-case performance. Give an algorithm and also quantify such a T(epsilon). Can you please justify why should the agent be penalized in an adversarial way in an "online manner" if the actual state-state transitions are happening according to the true MDP?

4 comments

Thank you for your review. We address the technical questions first.

W1/Q1. Existence of a maximizer.

The maximizer exists on the event used in the regret analysis. Under the theorem's sample-size conditions, the restricted confidence product contains PRP_R and lies in Kface(PR)\mathcal K_{\mathrm{face}}(P_R). Its row sets are closed subsets of finite-dimensional simplices, and all coordinates in the recovered support are uniformly positive. The support constraint therefore removes no point, and the feasible set is nonempty and compact. The uniform bias-span and row-continuity bounds give

\le H_{\mathrm{loc}}(P_R)K_{\mathrm{face}}(P_R)\\|Q-Q'\\|_{\max,1},$$ so the extreme value theorem gives attainment. To specify the algorithms on all histories, we will add an explicit fallback to $\pi_0$ for the episode if no maximizer exists. Under the stated sample-size conditions, this can occur only outside the confidence and exploration event, whose contribution is already bounded by $\alpha T$ in expectation. This completes the algorithm definition without changing the regret bounds. **W1/Q2. Existence of the eigenpair.** The eigenpairs required by Algorithms 2-3 are supplied by Theorem 3. Algorithm 2 checks the Bellman radius over its confidence product; Algorithm 3 uses the exit-mass certificate. Both ensure $\delta < \delta_f^{\mathrm{bell}}(Q_k)$ for the selected center and hence $$g_k\mathbf 1+h_k=\mathcal L^{\mathrm{rob}}_{Q_k}h_k.$$ The passage at lines 890-898 concerns a different operator, $\mathcal L_k$, in an auxiliary decomposition. That decomposition requires an eigenpair of $\mathcal L_k$; we will state this hypothesis explicitly there and in Theorem 8. The main regret proofs in Theorems 12-13 use the single-center equation above directly, through inequalities (62)-(63) and (74). They do not invoke the auxiliary decomposition. Thus a failure of eigenpair existence for $\mathcal L_k$ would not invalidate the main regret guarantees. **W2. State-action rectangularity.** This is an established uncertainty model in robust dynamic programming [1, 2] and robust RL. It is used across the following learning settings, which lead up to our work. | Setting | Published examples | | --- | --- | | Episodic online learning | Lu et al. [3], He et al. [4] | | Discounted learning | Wang et al. [5] (generative), Liang et al. [6] (single trajectory) | | Average-reward learning with a generative model | Chen et al. [7], Roch et al. [8] | For any coupled set $\mathcal U$, its rectangular hull satisfies $$\mathcal U\subseteq\prod_{s,a}\operatorname{proj}_{s,a}(\mathcal U).$$ For fixed row projections, rectangularity therefore gives the adversary at least as many possible row combinations and can lower a policy's worst-case gain. Coupling and rectangularity specify different models; the inclusion does not make their objectives equivalent. Our contribution is learning the center of this established rectangular model from one continuing nominal trajectory. The general objection that rectangularity is restrictive does not identify a defect in the results for that model. **W3/Q3. Exposition.** If accepted, we will add an earlier explanation of weak communication, a small example distinguishing the three thresholds, and a short sketch of policy completion. These additions will help readers follow the definitions and their role in the learning results. **References** 1. G. N. Iyengar. Robust Dynamic Programming. Mathematics of Operations Research, 2005. 2. A. Nilim and L. El Ghaoui. Robust Control of Markov Decision Processes with Uncertain Transition Matrices. Operations Research, 2005. 3. M. Lu, H. Zhong, T. Zhang, and J. Blanchet. Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms. NeurIPS, 2024. 4. Y. He, Z. Liu, W. Wang, and P. Xu. Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction. ICML, 2025. 5. S. Wang, N. Si, J. Blanchet, and Z. Zhou. Sample Complexity of Variance-Reduced Distributionally Robust Q-Learning. JMLR, 2024. 6. Z. Liang, X. Ma, J. Blanchet, J. Yang, J. Zhang, and Z. Zhou. Single-Trajectory Distributionally Robust Reinforcement Learning. ICML, 2024. 7. Z. Chen, S. Wang, and N. Si. Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning. NeurIPS, 2025. 8. Z. A. Roch, G. K. Atia, and Y. Wang. A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward. ICML, 2025.

W4/Q5. Policy regret and the requested sample complexity.

Learning under nominal transitions while evaluating robust policy values is also the formulation used in episodic online robust RL [5]. The distinction between the training dynamics and the evaluation dynamics is the purpose of the robust objective.

The requested final-policy guarantee follows from Algorithm 1 and Theorem 9. After mm steps of uniform nominal exploration, return its plug-in policy π^m\widehat\pi_m and deploy from the current state SmS_m. Under Theorem 9's assumptions, including support recovery and fixed-face accuracy, with probability at least 1−α1-\alpha,

\le 2H_{\mathrm{loc}}(P_R)K_{\mathrm{face}}(P_R)\beta_{\alpha/3}(n_m),$$ where $n_m:=\max\\{n\in\mathbb N_0:\mathfrak t_P(n,\alpha)\le m\\}$ and $\mathfrak t_P$ is the exploration clock in Appendix B.2. On fixed parameter-bounded families, this gives $\widetilde O(\epsilon^{-2})$ sufficient nominal interactions once the readiness conditions hold, with logarithmic confidence dependence. Policy regret also charges for the robust quality of policies used during learning, including exploration. A final-policy guarantee alone does not measure this cost. This distinction is central to the exploration cost producing the $T^{2/3}$ rate. It also has a direct deployment interpretation. Sample $J$ uniformly from $\\{0,\ldots,T-1\\}$ independently of the learning run, reveal it only when it occurs, and then commit to $\pi_J$ from $S_J$. Before handover the learner follows the original horizon-$T$ algorithm. Thus $$\mathbb E\\!\left[g^{\mathrm{rob}}(P)-g_{\mathrm{rob},P}^{\pi_J}(S_J)\right] =\frac{\mathbb E[\operatorname{Reg}_{\mathrm{pol}}(T)]}{T},$$ with the right-hand side defined for the uninterrupted nominal run. The two regret rates give expected robust deployment gaps $\widetilde O(T^{-1/2})$ and $\widetilde O(T^{-1/3})$, without returning to an earlier state. Section 5 distinguishes this criterion from accumulated realized rewards. We will make these deployment consequences explicit alongside Eq. (5). **Q4. Comparison with prior work.** The comparison below separates the data models and performance criteria. Our main distinction is learning from one nominal trajectory while identifying the structural conditions for matching policy-regret exponents. In particular, the square-root guarantee extends beyond both communication thresholds whenever $\delta_f^\dagger(P)\le\delta < \delta_f^{\mathrm{bell}}(P)$ is nonempty. We will include this comparison in the final version. | Work | Data and criterion | Main conditions | Guarantee | | --- | --- | --- | --- | | Lim et al. [1] | Continuing interaction; realized-reward regret | Some training rows adversarial; every admissible MDP communicating and unichain | $\widetilde O(\sqrt T)$ | | Wang and Si [2] | Fixed ambiguity set; robust optimality of a history-dependent controller | Adversary commits to one stationary kernel | Sublinear regret for every kernel suffices | | Chen et al. [3] | Generative samples; average-reward policy learning | Nominal uniform ergodicity; small-radius KL or $f_k$ balls | $\widetilde O(\epsilon^{-2})$ samples | | Liang et al. [4] | One nominal trajectory; discounted robust control | Cressie-Read balls | Asymptotic robust $Q$ convergence | | Ghosh et al. [5] | Nominal episodes; robust-value regret | Finite horizon; $\chi^2$ or KL balls; KL minimum-positive-probability bound | $\widetilde O(\sqrt K)$ | | **Ours** | One nominal trajectory; average-reward policy regret | No creation; $\delta < \delta_f^{\mathrm{bell}}(P)$ | $\widetilde\Theta(\sqrt T)$ | | **Ours** | One nominal trajectory; average-reward policy regret | Creation; nominal communication; below saturation | $\widetilde\Theta(T^{2/3})$ | $K$ denotes the number of episodes. Rates suppress other fixed parameters. Our matching claims concern $T$ on parameter-bounded families. The data models and criteria differ across rows; these are not bounds for a single common problem. **References** 1. S. H. Lim, H. Xu, and S. Mannor. Reinforcement Learning in Robust Markov Decision Processes. NeurIPS, 2013, Theorem 2. 2. S. Wang and N. Si. Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values. Preprint, arXiv:2603.00945, 2026. 3. Z. Chen, S. Wang, and N. Si. Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning. NeurIPS, 2025. 4. Z. Liang, X. Ma, J. Blanchet, J. Yang, J. Zhang, and Z. Zhou. Single-Trajectory Distributionally Robust Reinforcement Learning. ICML, 2024. 5. D. Ghosh, G. K. Atia, and Y. Wang. ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning. AAAI, 2026.

Thank you for your thoughtful comments. With the discussion period nearly over, we wanted to briefly follow up on our rebuttal. We have worked carefully to address each concern and would value hearing whether our responses resolve them and what further revisions or clarifications are still needed.

Reviewer_8fYPOpenReview ↗

Author response read and analyzed

I thank the authors for their effort in responding to my concerns. This addresses my concerns only partially. These do not completely address my concerns satisfactorily. Hence I stick to my score.

Comments on the paper

1 comment

We include a summary of points made by reviewers and how we addressed each.

  • Maximizer existence (8fYP W1/Q1). Follows from results already in the paper, as explained in rebuttal.

  • Eigenpair existence (8fYP W1/Q2). Concerns auxiliary result in a special case where existence is itself the hypothesis, not needed for any main paper results. Hypothesis can be added for clarity, or result can be removed entirely with no consequence.

  • Uncertainty sets and rectangularity (8fYP W2). Formulation and modeling scope further explained in rebuttal. Supplied examples across established robust RL settings as cited in the paper.

  • Policy regret and deployment interpretation (8fYP W4/Q5; H5ga W1/Q1; V9Dx Q1). Distinction from accumulated rewards already stated in main paper. Deployment interpretation and the role of exploration costs further explained in the rebuttal.

  • Policy suboptimality and sample complexity (8fYP W4/Q5; H5ga Q1; V9Dx Q1). Regret conversion and the finite sample consequence of Theorem 9 explained in rebuttal. Can be added for clarity as a direct corollary.

  • Exposition and weak communication property (8fYP W3/Q3; V9Dx W1). Will add an earlier explanation of weak communication, a threshold example, and clearer explanations of costly exploration and policy completion as more space is given.

  • Novelty and comparison with prior work (8fYP W3/Q4). Supplied comparison table summarizing related work section. This distinguishes data access, objectives, assumptions, and guarantees. Will be added to the main paper as more space is given.

  • Algorithmic conditions and structural margins (H5ga Q2). Existing conditions of paper consolidated into a sufficient horizon condition as requested. Included uniform family bounds and a KL example also as requested.

  • Policy completion and its proof role (H5ga Q3). Supplied the requested sketch linking the completion construction to the regret proof. Details shown explicitly in appendix. Sketch can be added to main text as more space is given.

  • Scope of matching rates (V9Dx W2). Scope already stated in the paper and further clarified in the rebuttal.

  • Computational complexity (V9Dx Q2). Information-theoretic scope already disclosed in the paper. Requested operation count supplied in the rebuttal.

We believe all concerns were addressed, and only minor edits are needed to improve readability and show further implications of our presented results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.