Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

📄 arXiv: 2405.20165v2 📥 PDF

作者: Wooseong Cho, Taehyun Hwang, Joongkyu Lee, Min-hwan Oh

分类: stat.ML, cs.LG

发布日期: 2024-05-30 (更新: 2024-10-31)

备注: Accepted in NeurIPS 2024

💡 一句话要点

提出随机化探索算法以解决多项逻辑函数近似的强化学习问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 多项逻辑函数 随机化探索 马尔可夫决策过程 算法优化 频率后悔

📋 核心要点

  1. 现有的强化学习方法在处理多项逻辑函数近似时，面临转移概率核未知和状态转移不均匀的挑战。
  2. 本文提出的$ exttt{RRL-MNL}$和$ exttt{ORRL-MNL}$算法通过随机化探索和乐观采样，确保了估计值函数的乐观性和频率保证。
  3. 实验结果表明，所提算法在性能上优于现有方法，尤其是在频率后悔界限和计算效率方面表现突出。

📝 摘要（中文）

本文研究了使用多项逻辑（MNL）函数近似的强化学习，其中马尔可夫决策过程（MDP）的转移概率核由未知的转移核心参数化，涉及状态和动作的特征。在有限时间的非均匀状态转移的情境下，提出了具有频率保证的随机化探索算法。第一个算法$ exttt{RRL-MNL}$通过乐观采样确保估计值函数的乐观性，达到了$ ilde{O}(κ^{-1} d^{ rac{3}{2}} H^{ rac{3}{2}} ext{sqrt}(T))$的频率后悔界限。为了改善对$κ^{-1}$的依赖，提出了$ exttt{ORRL-MNL}$，其后悔界限为$ ilde{O}(d^{ rac{3}{2}} H^{ rac{3}{2}} ext{sqrt}(T) + κ^{-1} d^2 H^2)$。这些算法是首个在MNL转移模型下实现统计保证的随机化强化学习算法。

🔬 方法详解

问题定义：本文旨在解决多项逻辑函数近似下的强化学习问题，特别是马尔可夫决策过程中的转移概率核未知和状态转移不均匀的挑战。现有方法在这些方面的表现不尽如人意，尤其是在频率后悔界限上存在较大依赖。

核心思路：论文的核心思路是通过引入随机化探索和乐观采样，确保估计值函数的乐观性，从而提高学习效率和收敛速度。特别是，$ exttt{ORRL-MNL}$算法利用局部梯度信息来改进值函数的估计，降低对$κ^{-1}$的依赖。

技术框架：整体架构包括两个主要算法：$ exttt{RRL-MNL}$和$ exttt{ORRL-MNL}$。前者通过乐观采样实现频率保证，后者则通过局部梯度信息优化值函数估计。算法的每个步骤都确保了常数时间的计算成本。

关键创新：最重要的技术创新在于首次提出了针对MNL转移模型的随机化强化学习算法，并且在常数时间内实现了统计保证。这一创新使得算法在实际应用中更具可行性和效率。

关键设计：算法设计中，关键参数包括转移核心的维度$d$、时间范围$H$和总步数$T$。损失函数和优化策略的选择确保了算法的收敛性和效率，特别是在处理复杂状态转移时的表现。

📊 实验亮点

实验结果显示，$ exttt{RRL-MNL}$和$ exttt{ORRL-MNL}$算法在频率后悔界限上分别达到了$ ilde{O}(κ^{-1} d^{ rac{3}{2}} H^{ rac{3}{2}} ext{sqrt}(T))$和$ ilde{O}(d^{ rac{3}{2}} H^{ rac{3}{2}} ext{sqrt}(T) + κ^{-1} d^2 H^2)$，在计算效率上保持常数时间，显著优于传统方法。

🎯 应用场景

该研究的潜在应用领域包括智能决策系统、自动化控制和机器人导航等。通过提高强化学习算法在复杂环境中的效率和可靠性，能够推动相关领域的技术进步和应用落地，具有重要的实际价值和未来影响。

📄 摘要（原文）

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, $\texttt{RRL-MNL}$, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency. We establish that $\texttt{RRL-MNL}$ achieves a $\tilde{O}(κ^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{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 $κ$ is a problem-dependent constant. Despite the simplicity and practicality of $\texttt{RRL-MNL}$, its regret bound scales with $κ^{-1}$, which is potentially large in the worst case. To improve the dependence on $κ^{-1}$, we propose $\texttt{ORRL-MNL}$, which estimates the value function using the local gradient information of the MNL transition model. We show that its frequentist regret bound is $\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + κ^{-1} d^2 H^2)$. 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.