stat.MLNov 3, 2026

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

Authors: Yue Wang

Organizations: University of Central Florida

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, SS states, AA actions, and mm known reward functions taking values in [0,1][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−γ)−1H=(1-γ)^{-1}, we establish the constant-confidence minimax sample complexity Θ~ ⁣(SAH3ε2min⁡{S,log⁡(em)})\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right), where the suppressed factors are logarithmic in S,A,H,ε−1S,A,H,\varepsilon^{-1} and the dependence on mm 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 H3ε−2H^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.

Figures & tables

Explore similar work

Sep 29, 2026

Optimal Multi-Reward Reinforcement Learning

We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions {r1,r2,…,rM}\{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 V0∗,m−V0π^m,mV_{0}^{*, m} - V_{0}^{\widehatπ^{m}, m} where m∈[M]m\in [M] represents the reward function and V0∗,m=Es1∼μ[V1∗,m(s1)]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(SAH3ε2log⁡Mpolylog(SAHlog⁡Mmin⁡{ε,1}δ)) 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 polylog(SAHlog⁡M/(min⁡{ε,1}δ)) \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.
Nov 14, 2026

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

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ε−2log⁡(SA/δ))O(SA (1-γ)^{-3} \varepsilon^{-2} \log(SA/δ)) samples, where S,A,γ,δ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ε−2log⁡(SA/δ))O(SAH\varepsilon^{-2}\log(SA/δ)) and O(SADε−2log⁡(SA/δ))O(SAD\varepsilon^{-2}\log(SA/δ)) complexities, respectively, where HH upper-bounds the optimal bias span and DD 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.
Oct 3, 2026

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

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 β≠0β\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 QQ-value function and an ε\varepsilon-optimal policy. Our bounds improve the exponential dependence on the effective horizon 1/(1−γ)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−γ)|β|/(1-γ), as well as in SS, AA, ε\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.