Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

We study reinforcement learning with multinomial logistic (MNL) function approximation where the underlying transition probability kernel of the Markov decision processes (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, textttRRL-MNL, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency. We establish that textttRRL-MNL achieves a tildeO(kappa-1 d^frac32 H^frac32 √T) frequentist regret bound with constant-time computational cost per episode. Here, d is the dimension of the transition core, H is the horizon length, T is the total number of steps, and kappa is a problem-dependent constant. Despite the simplicity and practicality of textttRRL-MNL, its regret bound scales with kappa-1, which is potentially large in the worst case. To improve the dependence on kappa-1, we propose textttORRL-MNL, which estimates the value function using the local gradient information of the MNL transition model. We show that its frequentist regret bound is tildeO(d^frac32 H^frac32 √T + kappa-1 d2 H2). To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve statistical guarantees with constant-time computational cost per episode. Numerical experiments demonstrate the superior performance of the proposed algorithms.