Regret minimization studies how an agent can learn an effective policy while keeping the cumulative reward it gives up, compared with an optimal or hindsight benchmark, as small as possible. Common approaches include optimistic exploration such as UCB, posterior or Thompson sampling, policy optimization, and primal-dual methods for constrained problems; variance-aware and gap-dependent analyses aim to improve guarantees when the environment is favorable. Work spans tabular finite- and infinite-horizon Markov decision processes, linear and kernel function approximation, adversarial or changing rewards, and settings with delayed, preference-based, or risk-sensitive feedback. Many settings now have near-matching upper and lower regret bounds, but a central tension remains between guarantees that adapt to problem structure and algorithms that remain computationally efficient under weaker assumptions.
Reinforcement learning with multinomial logistic (MNL) function approximation has become an important framework due to its flexibility and broad applicability. While existing studies have established regret guarantees under worst-case analysis, they do not capture how performance depends on the variability of the interaction between the learner and the environment. In this paper, we develop a new theoretical analysis for MNL-based Markov decision processes that yields explicit variance-adaptive regret bounds. Our algorithm is computationally efficient and achieves the instance-wise optimal rate of regret, narrowing the gap between upper and lower bounds. Our numerical experiments validate that our method learns optimal policies more efficiently than conventional approaches.
Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1
Chung-Ang University · Seoul National University · Columbia University
Human feedback often arrives as preferences rather than calibrated numeric rewards, motivating reinforcement learning from preferential feedback, also referred to as reinforcement learning from human feedback (RLHF). We present a rigorous theoretical study of preference-only learning in episodic kernel MDPs. In each episode, the learner deploys two policies from a common start state and receives a single binary label indicating which trajectory is preferred, modeled by a Bradley--Terry--Luce link on the difference of cumulative (unobserved) rewards. Under kernel-based assumptions on the reward and transition functions (one of the most general models amenable to theoretical analysis) we develop preference-based value estimation and confidence sets tailored to end-of-episode comparisons. We prove high-probability regret bounds that scale sublinearly in the number of episodes, implying that the value of the learned policy converges to that of the optimal policy.
We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of O~(dH2T) (Li et al., 2024), where d is the feature dimension, H the episode length, and T the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant σˉ_T≤1/2, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of O~(dH2σˉ_TT), which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs, σˉ_T=O(H−1), reducing the horizon dependence by a factor H. We further establish a matching Ω(dH2σˉ_TT) lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.
Pierre Boudart, Pierre Gaillard, Alessandro Rudi
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3
We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that are observed at the start of each episode. Performance is measured by cumulative regret against the episode-wise optimal value, ∑k=1K[V∗,Mk−Vπk,Mk], where Mk represents the action context in the k-th episode. We show that the MVP algorithm naturally extends to this framework and enjoys strong theoretical guarantees. In particular, we establish a minimax regret bound of O(SAH3KlogL) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of O(SAH3K) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of O(SAH3/ε2) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of
O(p∈[0,1)inf(Δminp1+pKΔminp)logK⋅poly(S,A,H)),
where Δminp is the global p-trimmed positive-gap floor over suboptimal (h,s,a) triples. This bound can substantially improve upon the minimax rate when the relevant suboptimality gaps are large.
Zijun Chen, Zihan Zhang
Department of Computer Science and Engineering Hong Kong University of Science and Technology
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of O(T2/3), improving upon the best known bounds, where T denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.
We present the first theoretical guarantees for differentially private online reinforcement learning (RL) with general function approximation, extending beyond prior work restricted to tabular and linear settings. Our approach combines a batched policy update scheme with the exponential mechanism, together with a novel regret analysis. We show that, even under general function approximation, the regret in the model-free setting under differential privacy matches the state of the art for the linear case, scaling as O(K3/5), where K denotes the number of episodes. As an important by-product, we also establish the first regret bound for online RL with batch update that depends on the standard complexity measure of coverability, complementing existing results based on a newly introduced Eluder-Condition class. In addition, we uncover fundamental gaps in recent results for private RL with linear function approximation, thereby clarifying its landscape.
We study the distribution of regret in stochastic multi-armed bandits and episodic reinforcement learning through a unified framework. We formalize a distributional regret bound as a probabilistic guarantee that holds uniformly over all confidence levels δ∈(0,1], thereby characterizing the regret distribution across the full range of δ. We present a simple UCBVI-style algorithm with exploration bonus min{c1,k/N,c2,k/N}, where N denotes the visit count and (c1,k,c2,k) are user-specified parameters. For arbitrary parameter sequences, we derive general gap-independent and gap-dependent distributional regret bounds, yielding a principled characterization of how the parameters control the trade-off between expected performance, tail risk, and instance-dependent behavior. In particular, our bounds achieve optimal trade-offs between expected and distributional regret in both minimax and instance-dependent regimes. As a special case, for multi-armed bandits with A arms and horizon T, we obtain a distributional regret bound of order O(ATlog(1/δ)), confirming the conjecture of Lattimore & Szepesvári (2020, Section 17.1) for the first time.
Harin Lee, Min-hwan Oh
University of Washington · Seoul National University
Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks, as conventional regret minimization algorithms require repeated, costly calls to planning and statistical estimation oracles. While recent advances have explored offline oracle-efficient algorithms, their computational complexity typically scales with the cardinality of the state and action spaces, rendering them intractable for large-scale or continuous environments. In this paper, we address this fundamental limitation by studying offline oracle-efficient episodic RL through the lens of log-barrier and log-determinant regularization. Specifically, for tabular Markov Decision Processes (MDPs), we propose a novel algorithm that achieves the optimal O~(T) regret bound while requiring only O(HloglogT) calls to both the offline statistical estimation and planning oracles when T is known and O(HlogT) calls when T is unknown. Crucially, this oracle complexity is entirely independent of the size of the state and action spaces. This strict independence drastically reduces the planning oracle complexity, representing a substantial improvement over existing offline oracle-efficient algorithms (Qian et al., 2024). Furthermore, we demonstrate the versatility of our framework by generalizing the algorithm to linear MDPs featuring infinite state spaces and arbitrary action spaces. We prove that this generalized approach successfully attains meaningful sub-linear regret. Consequently, our work yields the first doubly oracle-efficient (i.e., efficient with respect to both statistical estimation and policy optimization) regret minimization algorithm capable of solving MDPs with infinite state and action spaces, significantly expanding the boundaries of computationally tractable RL.
Haichen Hu, Jian Qian, David Simchi-Levi
Laboratory for Information and Decision Systems · Department of AI and Data Science
Reinforcement learning from human feedback (RLHF) is a central post-training tool for aligning large language models, but its training reward is only a learned proxy for true human utility. This creates a decision problem under objective misspecification: the policy is optimized against an estimated reward, while deployment performance is governed by an unobserved population preference. The resulting gap leads to reward over-optimization, where proxy reward keeps improving after true quality deteriorates. We propose distributionally robust regret optimization (DRRO) for RLHF with a Wasserstein ambiguity set over reward laws, using promptwise ℓp distances between reward vectors as transport costs. Unlike standard distributionally robust optimization, which pessimizes worst-case value, DRRO pessimizes worst-case regret relative to the best policy under the same plausible reward perturbation. We show that the expressive-policy problem decomposes into promptwise regret problems. For each prompt, the inner adversary has a dual-norm closed form; under the ℓ1 transport cost used by our algorithm, the optimizer has a water-filling structure. These results lead to a practical policy-gradient algorithm that adds a simple sampled bonus to GRPO-style training. Theory and experiments both show that DRRO is less over-pessimistic than standard DRO and mitigates over-optimization more effectively than existing baselines.
Yikai Wang, Shang Liu, Jose Blanchet
Department of Statistics and Operations Research, University of North Carolina · Imperial Business School, Imperial College London · Department of Management Science and Engineering, Stanford University
We study model-free reinforcement learning (RL) in non-stationary finite-horizon episodic Markov decision processes (MDPs) without prior knowledge of the non-stationarity. We focus on the piecewise stationary (PS) setting, where both rewards and transition dynamics can change at unknown times. We first revisit existing state-of-the-art approaches and identify theoretical and practical limitations that change the current landscape of performance guarantees. To characterize the difficulty of the problem, we establish the first minimax lower bounds for PS-RL in tabular and linear MDPs. We then introduce Detection Augmented Reinforcement Learning (DARLING), a modular wrapper for PS-RL that applies to both tabular and linear MDPs, without knowledge of the changes. In tabular MDPs, under change-point separability and reachability conditions, DARLING improves the best known dynamic regret bounds and matches our minimax lower bound. In linear MDPs, DARLING matches the minimax lower bound when the relevant reachability parameters are known, and our analysis clarifies the structural obstacles that distinguish this setting from the tabular case. Finally, through extensive experimentation across diverse non-stationary benchmarks, we show that DARLING consistently surpasses the state-of-the-art methods.
Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. Veeravalli
ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign
Robot reinforcement learning from demonstrations (RLfD) assumes that expert data is abundant; this is usually unrealistic in the real world given data scarcity as well as high collection cost. Furthermore, imitation learning algorithms assume that the data is independently and identically distributed, which ultimately results in poorer performance as gradual errors emerge and compound within test-time trajectories. We address these issues by introducing the "master your own expertise" (MYOE) framework, a self-imitation framework that enables robotic agents to learn complex behaviors from limited demonstration data samples. Inspired by human perception and action, we propose and design what we call the queryable mixture-of-preferences state space model (QMoP-SSM), which estimates the desired goal at every time step. These desired goals are used in computing the "preference regret", which is used to optimize the robot control policy. Our experiments demonstrate the robustness, adaptability, and out-of-sample performance of our agent compared to other state-of-the-art RLfD schemes. The GitHub repository that supports this work can be found at: https://github.com/rxng8/neurorobot-preference-regret-learning.
Viet Dung Nguyen, Yuhang Song, Anh Nguyen +3
Rochester Institute of Technology · Advanced Micro Devices, Inc. · University of Liverpool
Optimism in the face of uncertainty is a popular approach to balance exploration and exploitation in reinforcement learning. Here, we consider the online linear quadratic regulator (LQR) problem, i.e., to learn the LQR corresponding to an unknown linear dynamical system by adapting the control policy online based on closed-loop data collected during operation. In this work, we propose Intrinsic Rewards LQR (IR-LQR), an optimistic online LQR algorithm that applies the idea of intrinsic rewards originating from reinforcement learning and the concept of variance regularization to promote uncertainty-driven exploration. IR-LQR typically retains the structure of a standard LQR synthesis problem by only modifying the cost function, resulting in an intuitively pleasing, simple, computationally cheap, and efficient algorithm. This is in contrast to existing optimistic online LQR formulations that rely on more complicated iterative search algorithms or solve computationally demanding optimization problems. We show that IR-LQR achieves the optimal worst-case regret rate of T, and compare it to various state-of-the-art online LQR algorithms via numerical experiments carried out on an aircraft pitch angle control and an unmanned aerial vehicle example.
We propose a cross-fitted debiasing device for policy learning from offline data. A key consequence of the resulting learning principle is N regret even for policy classes with complexity greater than Donsker, provided a product-of-errors nuisance remainder is O(N−1/2). The regret bound factors into a plug-in policy error factor governed by policy-class complexity and an environment nuisance factor governed by the complexity of the environment dynamics, making explicit how one may be traded against the other.
We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes (CMDPs) with adversarial rewards under full-information feedback and an unknown transition kernel. We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds of O(d2H3K) under mild conditions, where d is the feature dimension, H is the horizon, and K is the number of episodes. To the best of our knowledge, this is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards. In particular, our regret bound is near-optimal, matching the known minimax lower bound up to logarithmic factors. The key idea is to introduce a regularized dual update that enables a drift-based analysis. This step is essential, as strong duality-based analysis cannot be directly applied when reward functions change across episodes. In addition, we extend weighted ridge regression-based parameter estimation to the constrained setting, allowing us to construct tighter confidence intervals that are crucial for deriving the near-optimal regret bound.
Kihyun Yu, Seoungbin Bae, Dabeen Lee
Department of Industrial and Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University · Research Institute of Mathematics, Seoul National University +2
In reinforcement learning, an agent interacts sequentially with an environment to maximize a reward, receiving only partial, probabilistic feedback. This creates a fundamental exploration-exploitation trade-off: the agent must explore to learn the hidden dynamics while exploiting this knowledge to maximize its target objective. While extensively studied classically, applying this framework to quantum systems requires dealing with hidden quantum states that evolve via unknown dynamics. We formalize this problem via a framework where the environment maintains a hidden quantum memory evolving via unknown quantum channels, and the agent intervenes sequentially using quantum instruments. For this setting, we adapt an optimistic maximum-likelihood estimation algorithm. We extend the analysis to continuous action spaces, allowing us to model general positive operator-valued measures (POVMs). By controlling the propagation of estimation errors through quantum channels and instruments, we prove that the cumulative regret of our strategy scales as O(K) over K episodes. Furthermore, via a reduction to the multi-armed quantum bandit problem, we establish information-theoretic lower bounds demonstrating that this sublinear scaling is strictly optimal up to polylogarithmic factors. As a physical application, we consider state-agnostic work extraction. When extracting free energy from a sequence of non-i.i.d. quantum states correlated by a hidden memory, any lack of knowledge about the source leads to thermodynamic dissipation. In our setting, the mathematical regret exactly quantifies this cumulative dissipation. Using our adaptive algorithm, the agent uses past energy outcomes to improve its extraction protocol on the fly, achieving sublinear cumulative dissipation, and, consequently, an asymptotically zero dissipation rate.
Josep Lumbreras, Ruo Cheng Huang, Yanglin Hu +2
Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Centre for Quantum Technologies, Nanyang Technological University, Singapore · QICI Quantum Information and Computation Initiative, School of Computing and Data Science, The University of Hong Kong, Pokfulam Road, Hong Kong SAR, China +2
Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the γ-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form O~(SAVar+lower-order terms), where S,A are the state and action space sizes, and Var captures cumulative transition variance. This implies minimax-optimal average-reward and γ-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span ∥h⋆∥sp, our algorithm obtains lower-order terms scaling as ∥h⋆∥spS2A, which we prove is optimal in both ∥h⋆∥sp and A. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than ∥h⋆∥sp2SA, and we provide a prior-free algorithm whose lower-order terms scale as ∥h⋆∥sp2S3A, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on ∥h⋆∥sp in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.
Guy Zamir, Matthew Zurek, Yudong Chen
Department of Computer Sciences, University of Wisconsin–Madison
Reinforcement learning from human feedback (RLHF) replaces hard-to-specify rewards with pairwise trajectory preferences, yet regret-oriented theory often assumes that preference labels are generated consistently from a single ground-truth objective. In practical RLHF systems, however, feedback is typically multi-source (annotators, experts, reward models, heuristics) and can exhibit systematic, persistent mismatches due to subjectivity, expertise variation, and annotation/modeling artifacts. We study episodic RL from multi-source imperfect preferences through a cumulative imperfection budget: for each source, the total deviation of its preference probabilities from an ideal oracle is at most ω over K episodes. We propose a unified algorithm with regret O~(K/M+ω), which exhibits a best-of-both-regimes behavior: it achieves M-dependent statistical gains when imperfection is small (where M is the number of sources), while remaining robust with unavoidable additive dependence on ω when imperfection is large. We complement this with a lower bound Ω~(max{K/M,ω}), which captures the best possible improvement with respect to M and the unavoidable dependence on ω, and a counterexample showing that naïvely treating imperfect feedback as oracle-consistent can incur regret as large as Ω~(min{ωK,K}). Technically, our approach involves imperfection-adaptive weighted comparison learning, value-targeted transition estimation to control hidden feedback-induced distribution shift, and sub-importance sampling to keep the weighted objectives analyzable, yielding regret guarantees that quantify when multi-source feedback provably improves RLHF and how cumulative imperfection fundamentally limits it.
Ming Shi, Yingbin Liang, Ness B. Shroff +1
Department of Electrical Engineering, University at Buffalo, Buffalo, NY 14260, USA · Department of Electrical and Computer Engineering, The Ohio State University, Columbus, OH 43210, USA · Department of Electrical and Computer Engineering and Computer Science and Engineering, The Ohio State University, Columbus, OH 43210, USA +1
We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm. Posterior sampling is a heuristic for decision-making under uncertainty that has been used to develop successful algorithms for a variety of continuous control problems. However, theoretical work on GP-PSRL is limited. All known regret bounds either have a sub-optimal growth rate, require strong smoothness assumptions, or fail to properly account for the fact that the set of possible system states is unbounded. Through a recursive application of the Borell-Tsirelson-Ibragimov-Sudakov inequality, we show that, with high probability, the states actually visited by the algorithm are contained within a ball of near-constant radius. We then use the chaining method to control the regret suffered by GP-PSRL under weak smoothness conditions. Our main result is a Bayesian regret bound of the order O(HγTT), where H is the horizon, T is the number of time steps and γT is the expected information gain. With this result, we resolve the limitations with prior theoretical work on PSRL, and provide the theoretical foundation and tools for analyzing PSRL in complex settings.
Hamish Flynn, Joe Watson, Ingmar Posner +1
Carnegie Mellon University · University of Oxford · Technical University of Darmstadt +2
We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of O~(HDmaxSAK), where S and A are the cardinalities of the state and action spaces, H is the time horizon, K is the number of episodes, and Dmax is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.
Harin Lee, Kevin Jamieson
Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, Washington.
Reinforcement learning algorithms are typically designed for generic Markov Decision Processes (MDPs), where any state-action pair can lead to an arbitrary transition distribution. In many practical systems, however, only a subset of the state variables is directly influenced by the agent's actions, while the remaining components evolve according to exogenous dynamics and account for most of the stochasticity. In this work, we study a structured class of MDPs characterized by exogenous state components whose transitions are independent of the agent's actions. We show that exploiting this structure yields significantly improved learning guarantees, with only the size of the exogenous state space appearing in the leading terms of the regret bounds. We further establish a matching lower bound, showing that this dependence is information-theoretically optimal. Finally, we empirically validate our approach across classical toy settings and real-world-inspired environments, demonstrating substantial gains in sample efficiency compared to standard reinforcement learning methods.
Davide Maran, Davide Salaorni, Marcello Restelli
Department of DEIB, Politecnico di Milano, Milan, Italy.
We study non-rectangular robust Markov decision processes under the average-reward criterion, where the ambiguity set couples transition probabilities across states and the adversary commits to a stationary kernel for the entire horizon. We show that any history-dependent policy achieving sublinear expected regret uniformly over the ambiguity set is robust-optimal, and that the robust value admits a minimax representation as the infimum over the ambiguity set of the classical optimal gains, without requiring any form of rectangularity or robust dynamic programming principle. Under the weak communication assumption, we establish the existence of such policies by converting high-probability regret bounds from the average-reward reinforcement learning literature into the expected-regret criterion. We then introduce a transient-value framework to evaluate finite-time performance of robust optimal policies, proving that average-reward optimality alone can mask arbitrarily poor transients and deriving regret-based lower bounds on transient values. Finally, we construct an epoch-based policy that combines an optimal stationary policy for the worst-case model with an anytime-valid sequential test and an online learning fallback, achieving a constant-order transient value.
Shengbo Wang, Nian Si
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology
We study computationally and statistically efficient reinforcement learning under the linear Qπ realizability assumption, where any policy's Q-function is linear in a given state-action feature representation. Prior methods in this setting are either computationally intractable, or require (local) access to a simulator. In this paper, we propose a computationally efficient online RL algorithm, named Frozen Policy Iteration, under the linear Qπ realizability setting that works for Markov Decision Processes (MDPs) with stochastic initial states, stochastic rewards and deterministic transitions. Our algorithm achieves a regret bound of O(d2H6T), where d is the dimensionality of the feature space, H is the horizon length, and T is the total number of episodes. Our regret bound is optimal for linear (contextual) bandits which is a special case of our setting with H=1. Existing policy iteration algorithms under the same setting heavily rely on repeatedly sampling the same state by access to the simulator, which is not implementable in the online setting with stochastic initial states studied in this paper. In contrast, our new algorithm circumvents this limitation by strategically using only high-confidence part of the trajectory data and freezing the policy for well-explored states, which ensures that all data used by our algorithm remains effectively on-policy during the whole course of learning. We further demonstrate the versatility of our approach by extending it to the Uniform-PAC setting and to function classes with bounded eluder dimension.
Yijing Ke, Zihan Zhang, Ruosong Wang
School of EECS, Peking University · Department of Computer Science and Engineering, HKUST · CFCS and School of Computer Science, Peking University
We consider the problem of regularized best-response max-regret minimization in online RLHF under general preferences and bandit feedback. While various regularizers are utilized to robustify alignment, known polylogarithmic regret guarantees remain heavily specific to KL. To investigate whether such fast rates extend beyond KL, we adopt the Generalized Bilinear Preference Model (GBPM) -- capturing intransitive preferences over d-dimensional item-wise features via a rank-2r skew-symmetric matrix -- to isolate the impact of generic regularization. Crucially, under GBPM, we prove that the dual gap of any greedy policy is bounded by the squared estimation error, derived using only strong convexity and skew-symmetry. Under a feature coverage assumption, we establish a generic polylogarithmic regret of O~(ηd4Cmin−1(logT)2∧d2Cmin−1/2T) with Greedy Sampling, and a dimension-wise improved regret (for well-conditioned arm-sets) of O~(Cmin−2ηrT∧r1/3Cmin−4/3T2/3) with Explore-Then-Commit, where η−1 is the regularization coefficient, T is the time horizon, and Cmin is an arm-set dependent quantity. This demonstrates that ``fast'' regrets are not KL-specific, but rather a fundamental consequence of generic strongly convex geometry.
We study gap-dependent regret for reinforcement learning with linear function approximation. While prior works have established gap-dependent guarantees in this setting, existing analyses do not apply to algorithms that achieve the nearly minimax-optimal worst-case regret bound O~(dH3K), where d is the feature dimension, H is the horizon length, and K is the number of episodes. We bridge this gap by establishing the first gap-dependent regret bound for the nearly minimax-optimal algorithm LSVI-UCB++ (He et al., 2023), with an expected regret bound O~(d2H3/Δmin+d6H5), improving the dependence on both d and H in the leading gap-dependent term compared with previous results. To understand the exploration cost induced by optimism, we establish a structural lower bound Ω(d2H3/Δmin) for a broad class of algorithms based on persistent ellipsoidal optimism. When specialized to LSVI-UCB++, this result shows that the leading dependence of our upper bound on d, H, and Δmin is tight up to logarithmic factors. Beyond this algorithmic class, we establish a general gap-dependent lower bound Ω(dH3logK/Δmin) for arbitrary learning algorithms, showing that the logarithmic dependence on K and the cubic dependence on H are intrinsic to gap-dependent expected regret in linear MDPs. Together, our results substantially narrow the gap between upper and lower bounds and provide a sharper characterization of gap-dependent learning and optimism-based exploration with linear function approximation.
Haochen Zhang, Zhong Zheng, Lingzhou Xue
Department of Statistics, The Pennsylvania State University · Department of Applied and Computational Mathematics and Statistics, University of Notre Dame
We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed εn-Greedy exploration scheme that combines εn-greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near-O~(N9/10). We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.
Rahul Singh, Siddharth Chandak, Eric Moulines +2
MBZUAI, UAE · Stanford University, USA · EPITA, France +1
This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic Q-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.
Mingyi Li, Taira Tsuchiya, Kenji Yamanishi
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · RIKEN AIP, Tokyo, Japan
Many operational Markov decision processes provide structured information where a trajectory generated under one policy may also reveal how other policies would have performed. We formalize this through an information order over a parameterized policy class, writing πθ′⪯πθ when data collected under πθ can be used to estimate the long-run average cost of πθ′. We develop an epoch-based reinforcement learning algorithm for infinite-horizon average-cost MDPs with continuous state and action spaces that exploits this order through counterfactual inference. For a d-dimensional policy class whose information order has width w, the algorithm achieves O(HwdT/α) regret relative to the optimal policy in the class, where H is a bias span upper bound and α denotes an "information ratio". Thus, the width captures the effective exploration complexity of the problem, interpolating between full counterfactual feedback and unstructured policy learning. We instantiate the framework in lost-sales inventory systems with positive lead times, dual-sourcing systems governed by dual-index policies, and queues with state-dependent service rates. These applications yield new regret guarantees without requiring global convexity of the average-cost function or specialized arrival-rate structure. Numerical experiments show that exploiting the information order substantially improves learning performance over existing general-purpose and problem-specific benchmarks.
Zhongjun Zhang, Shipra Agrawal, Ilan Lobel +2
Department of Industrial Engineering and Management Sciences, Northwestern University · Department of Industrial Engineering and Operations Research, Columbia University · Technology, Operations, and Statistics, Stern School of Business, New York University +1
Most learning algorithms with formal regret guarantees essentially rely on trying all possible behaviors, which is problematic when some errors cannot be recovered from. Instead, we allow the learning agent to ask for help from a mentor and to transfer knowledge between similar states. We show that this combination enables the agent to learn both safely and effectively. Under standard online learning assumptions, we provide an algorithm whose regret and number of mentor queries are both sublinear in the time horizon for Markov decision processes with irreversible dynamics and infinite state spaces. Our proof involves a sequence of three reductions, making our result more general than a single algorithm. Conceptually, our result may be the first formal proof that it is possible for an agent to obtain high reward while becoming self-sufficient in an unknown, unbounded, and high-stakes environment without resets.
Benjamin Plaut, Juan Liévano-Karim, Hanlin Zhu +1
Division of Computer Science University of California Berkeley, CA 94720-1776, USA
We study a structured class of Markov Decision Processes, known as Exo-MDPs, in which the state space is partitioned into exogenous and endogenous components. Exogenous states evolve stochastically, independent of the agent's actions, while endogenous states evolve deterministically based on both state components and actions. Exo-MDPs capture many operations research settings, including inventory control, resource management, and ride-sharing. Our first contribution is structural: we establish a representational equivalence between discrete MDPs, Exo-MDPs, and discrete linear mixture MDPs. Our second contribution is statistical. We characterize the minimax regret of learning in Exo-MDPs when the effective dimension r is small relative to the endogenous state and action spaces. When the exogenous states are unobserved, we prove matching upper and lower regret bounds of order Θ(HrK) over K episodes of horizon H, where r is the effective dimension of the Exo-MDP. When exogenous states are observed, the minimax regret improves to Θ(HrK), revealing a Θ(r) statistical gap due to observation of the exogenous states. These results show that Exo-MDPs decouple sample complexity from action space and endogenous state space. We validate these insights with experiments on inventory control and resource allocation.
Jia Wan, Sean R. Sinclair, Devavrat Shah +1
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology · Department of Industrial Engineering and Management Sciences, Northwestern University
This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.
Daniel Adelman, Cagla Keceli, Alba V. Olivares-Nadal
Booth School of Business, The University of Chicago, Chicago, IL 60637, USA · United Airlines, Chicago, IL 60605, USA · UNSW Business School, UNSW, Kensington NSW 2033, Australia