Metraipolis › archive › dc_a32e017e3909
Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05562
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:22:32.232Z
- SHA-256 of the archived text
64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97- Stable URL of this page
https://metraipolis.com/documento/dc_a32e017e3909
How to cite
Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562 — arXiv (en), https://arxiv.org/abs/2611.05562 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a32e017e3909 (Metraipolis archive dc_a32e017e3909, sha256 64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97)
BibTeX
@misc{dca32e017e3909,
title = {Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05562},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a32e017e3909; sha256 64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05562. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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-\gamma)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetilde\Theta\!\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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.05562 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:49.030Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).