Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak…

Abstract

We study distributionally robust reinforcement learning (DR-RL) in the average-reward setting under weak communication. Our main result provides finite-sample guarantees for estimating the robust optimal average reward and learning a near-optimal policy, covering both SA-rectangular and S-rectangular structures with divergence-based and distance-based uncertainty sets. Specifically, for Kullback--Leibler and f_k-divergence balls, we establish explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP to be weakly communicating. Our algorithm is prior-knowledge-free and achieves sample complexities of Õ(|𝒮||𝒜|p_∧⁻¹Span²(u_δ^∗)ε⁻²) for estimating the robust optimal average reward and Õ(|𝒮||𝒜|p_∧⁻²Span²(u_δ^∗)ε⁻²) for learning an ε-optimal policy. Here, p_∧ is the smallest positive nominal transition probability and u_δ^∗ is a robust optimal bias function. We further provide an almost-tight explicit upper bound on Span(u_δ^∗). Finally, we validate the predicted n^−1/2 convergence rate through numerical experiments.

Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
Huizhen Yu, Isaiah Heidt
arXiv7 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Improved Guarantees for Langevin Monte Carlo with Average Smoothness
Arnak S. Dalalyan, Avetik Karagulyan
HAL29 May 2026PreprintLicence not statedGeneral mathematicsHAL
Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
Zihang Liang, Haochen Zhang, Lingzhou Xue
arXiv1 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv
Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective
Yuhang Deng, Zheng Chen, Erik G. Larsson
arXiv23 Sep 2026PreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv
Distributionally Robust Federated Learning with Multi-Source Data
Yingzhu Liu, Zhongkui Li, Pengcheng You +1
arXiv17 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{lu2026distributionally,
  title = {{Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication}},
  author = {Chenyu Lu and Zijun Chen and Nian Si},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32727},
  eprint = {2609.32727},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32727},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
AU  - Chenyu Lu
AU  - Zijun Chen
AU  - Nian Si
PY  - 2026
DA  - 2026/09/26
PB  - arXiv
DO  - 10.48550/arxiv.2609.32727
UR  - https://arxiv.org/abs/2609.32727
AB  - We study distributionally robust reinforcement learning (DR-RL) in the average-reward setting under weak communication. Our main result provides finite-sample guarantees for estimating the robust optimal average reward and learning a near-optimal policy, covering both SA-rectangular and S-rectangular structures with divergence-based and distance-based uncertainty sets. Specifically, for Kullback--Leibler and f_k-divergence balls, we establish explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP to be weakly communicating. Our algorithm is prior-knowledge-free and achieves sample complexities of Õ(|𝒮||𝒜|p_∧^−1Span^2(u_δ^∗)ε^−2) for estimating the robust optimal average reward and Õ(|𝒮||𝒜|p_∧^−2Span^2(u_δ^∗)ε^−2) for learning an ε-optimal policy. Here, p_∧ is the smallest positive nominal transition probability and u_δ^∗ is a robust optimal bias function. We further provide an almost-tight explicit upper bound on Span(u_δ^∗). Finally, we validate the predicted n^−1/2 convergence rate through numerical experiments.
ER  -

Abstract

Related

Cite