acceptodds
Under review as a conference paper at ICLR 2027

Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes

Abstract

Robust average-reward Markov decision processes provide a fundamental framework for long-term performance optimization under uncertainty, and can have optimal long-run rewards that depend on the initial state. This state dependence requires a vector Bellman theory that accounts for both recurrent-class rewards and transition uncertainty. We develop such a theory for finite models with compact, post-action -rectangular ambiguity. A gain-first, bias-second optimization principle yields a coupled vector gain-bias system, and every finite solution identifies the optimal robust gain and supplies stationary saddle strategies against history-dependent opponents, simultaneously from all initial states. We further characterize solvability through stationary gain conditions and a uniform bound on canonical transient corrections, and give sufficient conditions that permit distinct recurrent-class gains. The certificates also yield asymptotically affine trajectories of the robust Bellman operator, based on which we design a robust approximately shifted Halpern planning algorithm. Under finite Bellman solvability, the gain estimates and Bellman displacements converge to the optimal gain vector, and every extracted greedy controller is average-optimal after a finite, instance-dependent budget. These results thus connect finite Bellman certificates to undiscounted planning for state-dependent robust average rewards, providing theoretical understandings.

Primary area:
reinforcement learning
Keywords:
robust MDPs, average reward, multichain, Bellman equations

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_WgogOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper addresses the question of vector Bellman theory for recurrent-class rewards and transition uncertainty. The authors consider the situation where a controller evolves in a Markov decision process whose dynamics are controlled by a second agent, called Nature, that selects the transitions in an adversarial way. They first extend previous results of Grand-Clément et al. (2023) on the averaged payoff to an all-state result with finite-horizon convergence. Then the authors extend the multichain gain-bias separation to the controller-Nature setting. The remainder of the paper consists of characterizing solvability for the fixed-value equation and for the full optimal-control system. Lastly, they present an algorithm to estimate the optimal robust gain and the optimal gain vector for a given policy.

Critical strengths

S1: The paper extends the “gain first, bias second” separation to the robust setting, imposing it on both the controller and Nature. Any finite solution of the resulting system yields the optimal robust gain and the optimal stationary strategies for both the controller and Nature.

S2: The authors propose an algorithm that works directly with the average reward and, when the system is solvable, approximates the optimal robust gain.

Critical weaknesses

W1: The paper can not be reviewed by a human. It relies on an extensively long appendix, full of equations and mathematical points. To understand the results, a reader has to study dozens of pages of the appendix. The contribution does not suit ICLR format. I recommend the authors to submit to an other venue.

W2: Section 3 does not appear particularly deep, and the proposed generalization of Grand-Clément et al. (2023) seems relatively straightforward.

W3: The exact criteria in Theorems 5.1 and 5.2 cannot be checked in practice.

W4: The iteration after which the extracted policy is optimal is only shown to exist; the paper provides no stopping rule or computable error bound.

W5: The numerical experiments only illustrate the theory on a very simple toy model. They neither test its practical value nor explore the results beyond the stated hypotheses.

Questions for authors

Q1. The sufficient conditions of Proposition 5.3 cover polytopic sets, for which planning methods already exist. Could the authors provide a summary of the uncertainty sets commonly used in the robust MDP and robust RL literature, indicating for each whether finite solvability is guaranteed?

Q2. Apart from polytopic sets and sets where the worst case never removes a transition, which commonly used uncertainty sets are covered by your results?

Q3. Would it be possible to obtain similar results in the case where Nature chooses its action based only on the controller’s state, before the controller acts?

Q4. Would it be possible to provide a stopping rule (see W3)?

Q5. Could you perform numerical experiments on larger environments, and study the performance of the algorithm when the assumptions are violated?

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

This paper considers robust average-reward MDPs. In the absence of additional assumptions, such as ergodicity or even weak communication, the paper develops a Bellman theory for finite models with compact, post-action (s,a)-rectangular ambiguity. The paper further characterize solvability of the Bellman equations. Based on this theory, the authors propose a robust approximately shifted Halpern planning algorithm, for which convergence guarantees are also provided.

Critical strengths
  1. The paper provides a comprehensive theory for the multi chain robust MDPs which was previously absent.
  2. The work provides an extensive discussion with existing literature.
  3. Novelty: While some of the techniques used are already known (e.g. Halperns iteration, vector Bellman theory), I do think there there are also novel and interesting components like the solvability characterizations.
Critical weaknesses
  1. The paper was quite challenging to read and understand, despite some familiarity with the topics. Mainly because of the amount of material included in one paper alone (it is 71 pages long). It may have been better as a journal submission.
Questions for authors
  1. Outside of the solvability characterizations, are there any other novelties in this work that are not found in existing literature?
Reviewer_pSFrOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper provides several theoretical results for average-reward robust MDP with finite states without the unichain assumption. The authors discuss both a gain vector obtained as a limit and the Bellman equation system which gain and bias should satisfy. They provide some sufficient conditions for the Bellman equation system to have a finite solution. They propose an iteration algorithm and prove its convergence under the assumption that the Bellman equation system has a finite solution. The convergence of the algorithm has been confirmed experimentally.

Critical strengths

This paper contains plenty results for this topic and they do not appear to be mere extensions of existing results, but rather seem to provide novel insights.

While there are numerous symbols in this paper, they are necessary and properly defined. Readers can follow the argument by reading carefully.

Critical weaknesses

This is too long as a conference paper. I know papers with long appendices are not rare in AI conferences, but I believe it is not good practice. In particular, the appendices of this paper seem to contain not only boring calculation or details for reproductivity but also some essential arguments. The main text contains only results and the informative arguments that lead readers to deeper understanding are missing.

The fact that the appendices form the bulk of the paper makes it difficult to review properly. I have not read most part of appendices because I have no time nor duty, but I do not believe it is enough. Especially, my choice to "I have no substantive concerns about the paper’s soundness" does not mean that I have verified soundness; it means that I have not verified anything. We must note that, even if a paper is accepted to conference where reviwers are not required to read appendices, it makes no guarantees concerning the contents of the appendices. The same holds true for the assessment of novelty; it is difficult to evaluate their theoretical significance solely by reading results.

Minor Comments:

  • A font of Q∗πQ^{\pi}_{*} immedieately after Theorem 5.1 is different.
  • There exist some missing spaces in the first paragraph of Section 6.

Update: After revising, some ideas of proofs are explained in main text and my concern has been resolved to some extent.

Questions for authors

None

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.