Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

我们研究了使用多项式逻辑函数逼近的强化学习，其中马尔可夫决策过程（MDP）的潜在转移概率核由具有状态和动作特征的未知转移核参数化。对于具有不同状态转移的有限时间段情景，我们提出了具有频率主义遗憾保证的随机探索的可证明高效算法。对于我们的第一个算法$\texttt{RRL-MNL}$，我们采用了乐观采样来确保估计值函数的乐观性，并证明了$\texttt{RRL-MNL}$在统计和计算效率方面都是高效的，每个情景的计算成本是恒定的，实现了$\tilde{O}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}}\sqrt{T})$的频率主义遗憾上界。其中，$d$是转移核的维数，$H$是时间段长度，$T$是总步数，$\kappa$是问题相关的常数。尽管$\texttt{RRL-MNL}$非常简单实用，但它的遗憾上界与$\kappa^{-1}$成比例，最坏情况下可能很大。为了改善对$\kappa^{-1}$的依赖关系，我们提出了$\texttt{ORRL-MNL}$，它使用MNL转移模型的局部梯度信息来估计值函数。我们证明了它的频率主义遗憾上界是$\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2)$。据我们所知，这些是首个针对MNL转移模型的随机强化学习算法，它们实现了计算和统计效率。数值实验证明了所提出算法的卓越性能。

本论文旨在解决具有多项式逻辑（MNL）函数逼近的强化学习问题，其中MDP的转移概率核由具有状态和动作特征的未知转移核参数化。

论文提出了两种随机探索的高效算法，分别为RRL-MNL和ORRL-MNL，能够有效地估计值函数并具有频率后悔保证。其中，ORRL-MNL通过使用MNL转移模型的局部梯度信息来估计值函数，改善了频率后悔与问题相关常数的依赖关系。

本论文提出的两种算法都能够在计算和统计效率上具有保证，且在实验中表现出色。此外，论文还是第一篇针对MNL转移模型的随机RL算法，值得进一步研究。

与本论文相关的研究包括：'Efficient Reinforcement Learning with Approximated Value Iteration for Decentralized POMDPs'、'Efficient Reinforcement Learning with Monte-Carlo Tree Search'等。