Metraipolis › archive › dc_5b360dc42d2b

Optimal Multi-Reward Reinforcement Learning — arXiv:2609.36486

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.36486
License (as archived)
CC0-1.0
Archived
2026-10-07T17:29:06.534Z
SHA-256 of the archived text
f938c1017efb0a7e84799327d29e38e58f2f206e8a22da8add71911ff92b6d86
Stable URL of this page
https://metraipolis.com/documento/dc_5b360dc42d2b

How to cite

Optimal Multi-Reward Reinforcement Learning — arXiv:2609.36486 — arXiv (en), https://arxiv.org/abs/2609.36486 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5b360dc42d2b (Metraipolis archive dc_5b360dc42d2b, sha256 f938c1017efb0a7e84799327d29e38e58f2f206e8a22da8add71911ff92b6d86)
BibTeX
@misc{dc5b360dc42d2b,
  title = {Optimal Multi-Reward Reinforcement Learning — arXiv:2609.36486},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.36486},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5b360dc42d2b; sha256 f938c1017efb0a7e84799327d29e38e58f2f206e8a22da8add71911ff92b6d86},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36486. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\epsilon$-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error $V_{0}^{*, m} - V_{0}^{\widehat\pi^{m}, m}$ where $m\in [M]$ represents the reward function and $V_{0}^{*, m}=\mathbb{E}_{s_1\sim \mu}[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}{\epsilon^2}\log M \mathrm{polylog}\left(\frac{SAH\log M}{\min\left\{\epsilon, 1\right\}\delta}\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\{\epsilon, 1\right\}\delta))$. 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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-30 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.36486 — 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-10-07T16:59:48.173Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).