Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation
<|reference_start|>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 $\tilde{\mathcal{O}}(dD\sqrt{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 $\tilde{\mathcal{O}}(d(1-\gamma)^{-2}\sqrt{T})$ regret where $\gamma$ is the discount factor. Then we complement these upper bounds by providing several regret lower bounds. We prove a lower bound of $\Omega(d\sqrt{DT})$ for learning communicating MDPs of diameter $D$ and a lower bound of $\Omega(d(1-\gamma)^{3/2}\sqrt{T})$ for learning discounted-reward MDPs with discount factor $\gamma$. Lastly, we show a regret lower bound of $\Omega(dH^{3/2}\sqrt{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.<|reference_end|>
@article{park2024infinite-horizon,
    title={Infinite-Horizon Reinforcement Learning with Multinomial Logistic
  Function Approximation},
    author={Jaehyun Park, Junyeop Kwon, Dabeen Lee},
    journal={arXiv preprint arXiv:2406.13633},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.13633},
    primaryClass={cs.LG math.OC}
}