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

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 ε-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−γ)⁻¹, we establish the constant-confidence minimax sample complexity Θ̃ ( SAH³/ε²min{S,log(em)} ), where the suppressed factors are logarithmic in S,A,H,ε⁻¹ 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³ε⁻² 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.

Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh Talebi
arXiv3 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Minimax-Optimality of Posterior Sampling for Reinforcement Learning
Taewon Goo, Kihyuk Hong
arXiv27 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
Naoki Nishikawa, Taiji Suzuki
arXiv6 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
Haichen Hu, David Simchi-Levi
arXiv25 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Minimax Rates for Conditional Generative Learning under Wasserstein Loss
Sungwon Park, Kyoung-Sook Moon, Hongjoong Kim
arXiv26 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{wang2026nearminimax,
  title = {{Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models}},
  author = {Yue Wang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05562},
  eprint = {2611.05562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05562},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models
AU  - Yue Wang
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05562
UR  - https://arxiv.org/abs/2611.05562
AB  - 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 ε-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 Θ̃ ( SAH^3/ε^2min{S,log(em)} ), where the suppressed factors are logarithmic in S,A,H,ε^−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ε^−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.
ER  -

Abstract

Related

Cite