The paper introduces a framework for reinforcement learning in Markov decision processes where policies are ordered by the information they provide, allowing data from one policy to estimate the performance of others. An epoch‑based algorithm is developed for infinite‑horizon average‑cost MDPs with continuous state and action spaces, achieving regret that scales with the width of the policy class’s information order. The authors apply the framework to lost‑sales inventory, dual‑sourcing, and state‑dependent queueing systems, demonstrating improved regret bounds and empirical performance without requiring global convexity or specific arrival‑rate structures.
By Zhongjun Zhang, Shipra Agrawal, Ilan Lobel, Sean R. Sinclair, Christina Lee Yu
arXiv:2602. 00781v2 Announce Type: replace Abstract: Online reinforcement learning in non-episodic, finite-horizon MDPs remains underexplored and is challenged by the need to estimate returns to a fixed terminal time.
By Jiamin Xu, Kyra Gan
arXiv:2610.32887v1 Announce Type: new
Abstract: Multi-step predictions of future transition realizations can improve reinforcement learning, but their value remains difficult to quantify. Directly in...
By Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman
The paper investigates reinforcement learning with multi‑step transition look‑ahead, where an agent can foresee the states resulting from any sequence of λ actions before choosing its next move. It proves that exact planning remains NP‑hard for every fixed rational discount factor γ in (0,1), and introduces a randomized polynomial‑time approximation scheme that works for any fixed look‑ahead depth. Extending this to unknown transitions and stochastic rewards, the authors develop an algorithm with cumulative regret matching classical tabular discounted RL up to logarithmic factors, showing that efficient near‑optimal planning and learning are achievable despite the NP‑hardness of exact planning.
By Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet
arXiv:2603. 03480v2 Announce Type: replace Abstract: We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps.
By Harin Lee, Kevin Jamieson
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require c...
The paper introduces a framework for optimal policy improvement in reinforcement learning, defining it as the best single update under given constraints. It shows that restricting improvement to a subset of states is equivalent to solving an induced Markov Decision Process, linking planning with explicit or implicit models to optimal policy improvement. The authors develop a novel operator for greedification under approximate evaluation, demonstrating empirical gains across several RL algorithms and settings.
By Yaniv Oren, Viliam Vadocz, Wiktor Zabka, Thomas Evers, Jan Robine, Wendelin B\"ohmer, Matthijs T. J. Spaan, Martha White, Hendrik Baier, Fenghui Yu
arXiv:2610. 08745v1 Announce Type: new Abstract: We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set.
By Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar Vakili
The paper introduces a computationally efficient algorithm for infinite-horizon average-reward constrained Markov decision processes (CMDPs) under weak communication. It achieves a high-probability regret and cumulative constraint violation of ×O(√T) in the tabular setting, matching optimal dependence up to logarithmic factors. The method augments the state with cumulative constraint violation, reshapes rewards using a Huber potential, and applies finite-horizon approximation with optimistic value iteration to maintain bounded per-step rewards.
By Kihyun Yu, Seoungbin Bae, Dabeen Lee
The paper introduces a reinforcement learning framework that selects among a portfolio of gradient‑based and derivative‑free optimizers during a run. At each decision point a recurrent policy reads the current run state and chooses both the next optimizer and its usage duration, passing the best solution and step size forward. The method is trained with a decoupled actor‑critic using the same runtime distribution metric as evaluation, and on unseen problems it outperforms all individual portfolio optimizers except at the smallest budgets, remaining robust to distribution shift.
By Martin van der Schelling, Deepesh Toshniwal, Miguel A. Bessa
arXiv:2510. 19528v2 Announce Type: replace-cross Abstract: We investigate the fundamental problem of leveraging offline data to accelerate online reinforcement learning - a direction with strong potential but limited theoretical grounding.
By Sebastian Reboul, H\'el\`ene Halconruy
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