Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation

We study model-based reinforcement learning with non-linear function approximation where the transition function of the underlying Markov decision process (MDP) is given by a multinomial logistic (MNL) model. We develop a provably efficient discounted value iteration-based algorithm that works for both infinite-horizon average-reward and discounted-reward settings. For average-reward communicating MDPs, the algorithm guarantees a regret upper bound of tildeO(dD√T) where d is the dimension of feature mapping, D is the diameter of the underlying MDP, and T is the horizon. For discounted-reward MDPs, our algorithm achieves tildeO(d(1-γ)-2√T) regret where γ is the discount factor. Then we complement these upper bounds by providing several regret lower bounds. We prove a lower bound of Omega(d√DT) for learning communicating MDPs of diameter D and a lower bound of Omega(d(1-γ)3/2√T) for learning discounted-reward MDPs with discount factor γ. Lastly, we show a regret lower bound of Omega(dH3/2√K) for learning H-horizon episodic MDPs with MNL function approximation where K is the number of episodes, which improves upon the best-known lower bound for the finite-horizon setting.