arXiv:2602. 09474v2 Announce Type: replace Abstract: We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of $\Lambda$ steps per episode.
By Ofir Schlisselberg, Tal Lancewicki, Yishay Mansour
arXiv:2607. 19854v1 Announce Type: new Abstract: We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.
By Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon S. Du
The paper introduces a novel technique called introduced feedback delays to address regret minimization in episodic Adversarial Markov Decision Processes (AMDPs). By estimating the Q‑function using future episodes while updating the policy, the authors achieve σO(poly(H)√{SAK}) regret in tabular AMDPs and σO(poly(d,H)√{K}) regret in linear AMDPs, resolving long‑standing open problems. The method also extends to delayed AMDPs, providing optimal bounds in terms of state count and total delay.
The paper introduces a technique called introduced feedback delays to improve regret bounds in episodic adversarial Markov Decision Processes (AMDPs). By estimating the Q‑function using future episodes while still updating the policy, the authors achieve µO(poly(H)√{SAK}) regret for tabular AMDPs and µO(poly(d,H)√{K}) regret for linear AMDPs, resolving long‑standing gaps. The method also extends to settings with actual feedback delays, providing optimal bounds in both state and delay dimensions.
By Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai
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:2610.02520v1 Announce Type: cross
Abstract: We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constrai...
By Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili
arXiv:2610.03165v1 Announce Type: new
Abstract: Several variance-reduced versions of REINFORCE based on importance sampling achieve an improved $O(\epsilon^{-3})$ sample complexity to find an $\epsil...
By Gabor Paczolay, Matteo Papini, Alberto Maria Metelli, Istvan Harmati, Marcello Restelli
The paper extends dueling bandits to episodic Markov decision processes where selecting a pair of arms not only yields a noisy preference but also influences the next state. It defines a state‑wise preference‑based MDP with adversarially changing preferences and Borda‑score losses, and proves a minimax regret of ∫Θ(min{HT,(H^3SK)^{1/3}T^{2/3}}) under known transitions. The authors provide an online linear‑optimization algorithm achieving this bound, a policy‑optimization algorithm with closed‑form updates, and extensions to unknown transitions.
By Taira Tsuchiya, Shinji Ito, Haipeng Luo
The paper introduces a new algorithm for a nonstationary bandit setting where actions influence both immediate rewards and the evolution of an unobserved latent linear state. By approximating the infinite‑memory reward process with a finite‑memory block‑level proxy and applying a UCB‑based block algorithm, the authors achieve a regret bound of “~O(√T)”, improving upon the previous “~O(T^{2/3})” guarantee. This represents the first such “~O(√T)” result for latent linear‑dynamics bandits with bilinear rewards and an open‑loop action‑sequence benchmark.
By Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh
arXiv:2608. 12753v1 Announce Type: new Abstract: We study decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under three forms of information asymmetry: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards.
By Larissa Xu, King Bi, William Chang
arXiv:2605.15692v2 Announce Type: replace-cross
Abstract: We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that a...
By Zijun Chen, Zihan Zhang
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