CS Paper Radar

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models

Yue Wang

cs.LG stat.ML ·submitted 2026-11-03 19:54 UTC · v1
theory

Abstract

In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, $S$ states, $A$ actions, and $m$ known reward functions taking values in $[0,1]$, given access to a generative model. The learner must provide an $\varepsilon$-optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing $H=(1-γ)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right)$, where the suppressed factors are logarithmic in $S,A,H,\varepsilon^{-1}$ and the dependence on $m$ is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state--action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the $H^3\varepsilon^{-2}$ dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.

Comment
Preprint, work in progress

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Multi-Reward Reinforcement Learning

cs.LG stat.ML ·2026-09-29 ·Zijun Chen, Zihan Zhang
theory similarity 0.76
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\}$. The goal is to output an $ε$-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error $V_{0}^{*, m} - V_{0}^{\widehatπ^{m}, m}$ where $m\in [M]$ represents the reward function and $V_{0}^{*, m}=\mathbb{E}_{s_1\sim μ}[V_{1}^{*, m}(s_1)]$. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of $$ O\left(\frac{SAH^3}{ε^2}\log M \mathrm{polylog}\left(\frac{SAH\log M}{\min\left\{ε, 1\right\}δ}\right)\right)$$ episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of $ \mathrm{polylog}(SAH\log M/(\min\left\{ε, 1\right\}δ))$. Our method combines three technical ingredients. First, we adapt MVP to reward-switching learning to construct optimistic value estimates. Second, we use fresh replay samples to conservatively evaluate the candidate policies. Third, gap-based multiplicative weights updates adjust the reward-sampling distribution using the differences between these estimates, converting weighted learning progress into simultaneous guarantees for all rewards.

0.47

Sharp Sample Complexity of KL-Regularized Reinforcement Learning

cs.LG cs.AI ·2026-11-10 ·Andrew Liu
theory similarity 0.75
Abstract

KL-regularized reinforcement learning, the objective behind maximum-entropy RL and RL from human feedback, is variational inference in the graphical model of "control as inference": the regularized optimal policy is a posterior over trajectories, and the suboptimality of a policy is $β$ times a KL divergence between path measures. However, it is not known how many samples it takes to learn this posterior, even with a generative model. Earlier $1/ε$ guarantees scale with $H^5$ in the effective horizon $H$, and no lower bound for MDPs depends on the temperature $β$. In this work, we show that for a discounted MDP with $K$ state-action pairs, the plug-in estimator finds a policy that is $ε$-optimal from every initial state with $\widetilde{O}(KH^3/(ε\max\{ε,β\}) + KH)$ samples, and that no algorithm, even one that chooses where to sample, can do with fewer when $ε\lesssim \min\{H, H^2/β\}$. For $ε< β$ this is a $1/ε$ rate with the same horizon dependence as unregularized RL. We also find the exact asymptotic constant of the plug-in estimator, a Fisher-weighted variance of the estimated soft Q-function. The estimator is locally asymptotically minimax among methods that sample every pair equally often, and we give the allocation of samples that is optimal among adaptive designs. Simulations on small MDPs match the rates and the constants.

0.36

Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

cs.LG stat.ML ·2026-10-03 ·Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh Talebi
similarity 0.73
Abstract

In this paper, we study the sample complexities of value and policy learning in finite discounted Markov decision processes (MDPs) under recursive entropic risk preferences with risk parameter \(β\neq 0\), assuming access to a generative model of the MDP. We provide a refined analysis of model-based risk-sensitive Q-value iteration (MB-RS-QVI), a plug-in model-based method introduced in prior work, and derive \((\varepsilon,δ)\)-PAC guarantees for both learning the optimal \(Q\)-value function and an \(\varepsilon\)-optimal policy. Our bounds improve the exponential dependence on the effective horizon \(1/(1-γ)\) compared with the best existing guarantees for this setting. In particular, they match the existing lower bounds in their exponential dependence on \(|β|/(1-γ)\), as well as in \(S\), \(A\), \(\varepsilon\), and \(|β|\), up to logarithmic factors. Consequently, our analysis removes the exponential gap between the previously known upper and lower bounds, leaving only a polynomial gap in the effective horizon.

0.13

Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

cs.LG cs.ITmath.OCmath.PR+1 ·2026-11-14 ·Matthew Zurek, Yudong Chen
similarity 0.72
Abstract

We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an $\varepsilon$-optimal policy with $O(SA (1-γ)^{-3} \varepsilon^{-2} \log(SA/δ))$ samples, where $S, A, γ, δ$ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve $O(SAH\varepsilon^{-2}\log(SA/δ))$ and $O(SAD\varepsilon^{-2}\log(SA/δ))$ complexities, respectively, where $H$ upper-bounds the optimal bias span and $D$ is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.

0.15

Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs

cs.LG math.OC ·2026-10-02 ·Enes Arda, Atilla Eryilmaz
top venue similarity 0.70
Abstract · NeurIPS 2026 camera-ready version. 45 pages, 5 figures

Policy mirror descent (PMD) has a mature finite-time theory in discounted Markov decision processes (MDPs), but less is known in the average-reward setting, a more natural objective for many control applications. We give a finite-time, finite-sample analysis of PMD in ergodic average-reward MDPs built around a single master recursion that governs convergence for any critic, without external regularization. Its specializations yield linear rates for exact, inexact-tabular, and linear function approximation (LFA) updates. For exact PMD, the rate is tight in the worst case, and convergence can become superlinear. We complement these convergence results with critics whose end-to-end sample complexities improve the prior best policy-gradient dependence from $|S||A|\,t_{\mathrm{mix}}^3$ to $|S|\,t_{\mathrm{mix}}^3+|S||A|\,t_{\mathrm{mix}}^2$ in the tabular setting and from $|S||A|\,t_{\mathrm{mix}}^5$ to $d\,t_{\mathrm{mix}}^3$ under LFA. Matching information-theoretic lower bounds establish that both critics are optimal up to logarithmic factors.

0.37

Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

cs.LG stat.ML ·2026-10-19 ·Victor Boone, Cyrille Kone, Waris Radji, Odalric-Ambrym Maillard, Dorian Baudry
theory similarity 0.67
Abstract

We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce $π_0$-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy $π_0$ during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for $π_0$-PSRL, identifying the logarithmic exploration cost induced by $π_0$ and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.

0.12

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

cs.LG stat.ML ·2026-09-27 ·Taewon Goo, Kihyuk Hong
similarity 0.67
Abstract · 44 pages

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax $\widetilde{O}(\sqrt{SAH^3K})$ regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax $\widetilde{O}(d\sqrt{H^3K})$ rate for linear-mixture MDPs under arbitrary joint parameter priors.

0.26

The Statistical Benefits of Multiple Responses for Learning from Demonstrations

cs.IT stat.MLcs.LGmath.ST ·2026-09-27 ·Chandramauli Chakraborty, Cong Ma
hot direction similarity 0.67
Abstract

Many generative systems return multiple candidate responses and are evaluated according to the best one. Recent work shows that, when demonstrations are optimal, pass@$k$ can reduce the sample complexity of learning from demonstrations by a logarithmic factor in $k$. We ask what happens when the demonstrator is not assumed to be optimal. We find that multiple responses provide a qualitatively stronger benefit in this setting. In a finite reward-class model with no reward feedback, moving from pass@$1$ to any pass@$k$ with $k\ge2$ changes the worst-case dependence on target accuracy from $1/\varepsilon^2$ to $1/\varepsilon$, uniformly over demonstrator quality. Under standard evaluation, where an unknown reward is fixed before training, increasing $k$ provides an additional and distinct benefit: the optimal dependence on a reward class of size $N$ improves from $\log N$ to $\log N/\log k$. We further show that these two effects can be separated. Under robust evaluation, where one learned policy must compete with the demonstrator simultaneously for every reward in the class, the fast $1/\varepsilon$ dependence persists, while the $1/\log k$ improvement can disappear. We establish matching upper and lower bounds in the corresponding regimes and give a greedy multiplicative-weights learner achieving the upper bounds without any assumption on demonstrator quality.

0.26