The paper investigates best‑policy identification in finite‑horizon, risk‑sensitive reinforcement learning using the entropic risk measure. It identifies a gap between known lower bounds ≥ η(e^{|eta|H}) and upper bounds ≤ O(e^{2|eta|H}) for sample complexity, attributing the excess factor to loose concentration bounds for exponential utilities. By employing a forward‑model algorithm with KL‑based exploration bonuses and a novel stopping rule, the authors achieve a sample complexity that matches the lower bound, closing the previously open exponential gap.
By Amer Essakine, Claire Vernade
arXiv:2302.07477v4 Announce Type: replace
Abstract: We study the optimal sample complexity of tabular reinforcement learning for infinite-horizon discounted Markov decision processes. The unrestricte...
By Shengbo Wang, Jose Blanchet, Peter Glynn
arXiv:2509. 16586v2 Announce Type: replace Abstract: Recent advances have significantly improved our understanding of the sample complexity of learning in average-reward Markov decision processes (AMDPs) under the generative model.
By Yukuan Wei, Xudong Li, Lin F. Yang
arXiv:2603. 08287v2 Announce Type: replace-cross Abstract: We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm.
By Hamish Flynn, Joe Watson, Ingmar Posner, Jan Peters
arXiv:2610.03642v1 Announce Type: new
Abstract: Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability...
By Matthew Brun, Xu Andy Sun
arXiv:2610. 12153v1 Announce Type: new Abstract: We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints.
By Qian Zuo, Francesco Emanuele Stradi
The paper addresses policy optimization in online episodic tabular MDPs with adversarial losses and bandit feedback. By employing regularized Q‑functions, the authors eliminate the extra horizon factor present in previous policy‑optimization regret bounds, achieving high‑probability regret of ≥O(√{HS(H+A)T}) for known transitions and ≥O(HS√{AT}) for unknown transitions. These results improve horizon dependence and match the best-known bounds, with extensions to adversarial linear‑mixture MDPs.
By Mingyi Li, Taira Tsuchiya
arXiv:2606. 25170v1 Announce Type: cross Abstract: We study PAC learning in tabular discounted Markov decision processes with exogenous i.
By Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet
arXiv:2606. 16729v1 Announce Type: new Abstract: While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model.
By Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal
arXiv:2609.37660v1 Announce Type: new
Abstract: We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a $d$-dimensional context vector; in each roun...
By Wansoo Choi, Seoungbin Bae, Dabeen Lee
arXiv:2607. 22982v1 Announce Type: new Abstract: Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success.
By Asha Barua, Sajad Khodadadian
arXiv:2609.36486v1 Announce Type: new
Abstract: We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions $\{r^1, r^2, \ldots, r^M...
By Zijun Chen, Zihan Zhang