Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
For researchers in reinforcement learning, this work provides a theoretically optimal algorithm that adapts to problem variance, improving efficiency over worst-case approaches.
This paper develops a variance-adaptive algorithm for reinforcement learning with multinomial logit function approximation, achieving instance-wise optimal regret rates and narrowing the gap between upper and lower bounds. Numerical experiments show faster learning of optimal policies compared to conventional methods.
Reinforcement learning with multinomial logistic (MNL) function approximation has become an important framework due to its flexibility and broad applicability. While existing studies have established regret guarantees under worst-case analysis, they do not capture how performance depends on the variability of the interaction between the learner and the environment. In this paper, we develop a new theoretical analysis for MNL-based Markov decision processes that yields explicit variance-adaptive regret bounds. Our algorithm is computationally efficient and achieves the instance-wise optimal rate of regret, narrowing the gap between upper and lower bounds. Our numerical experiments validate that our method learns optimal policies more efficiently than conventional approaches.