{"id":"arxiv/2605.19768","url":"https://arxiv.org/abs/2605.19768","tags":["cs.AI","cs.LG","math.ST","stat.ML"],"score":0,"title":"Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs","domain":"cs.AI","source":"arxiv","authors":["Pierre Boudart","Pierre Gaillard","Alessandro Rudi"],"reviews":0,"subject":"cs.AI","summary":"We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of $\\smash{\\tilde{O}(dH^2\\sqrt{T})}$ (Li et al., 2024), where $d$ is the feature dimension, $H$ the episode length, and $T$ the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant $\\barσ\\_T \\leq 1/2$, measuring the normalised average variance of the optimal downstream value…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-19","reactions":{}}