Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs

📄 arXiv: 2310.11515v1 📥 PDF

作者: Yu-Heng Hung, Ping-Chun Hsieh, Akshay Mete, P. R. Kumar

分类: cs.LG

发布日期: 2023-10-17

💡 一句话要点

提出值偏置最大似然估计以解决线性MDP中的计算效率问题

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

关键词: 线性马尔可夫决策过程 最大似然估计 值偏置 计算效率 优化算法 自适应控制 在线学习

📋 核心要点

  1. 现有基于回归的方法在处理大规模线性MDP时计算效率低下，导致优化运行次数过多。
  2. 本文提出值偏置最大似然估计（VBMLE），通过简化优化过程提高计算效率，解决线性MDP中的闭环识别问题。
  3. 实验结果显示，VBMLE在经验遗憾和计算时间上显著优于传统方法，验证了其有效性。

📝 摘要（中文）

本文考虑了无限期线性马尔可夫决策过程（MDP），其中动态模型的转移概率可以通过预定义的低维特征映射进行线性参数化。尽管现有的基于回归的方法在理论上已被证明能够实现近乎最优的遗憾，但由于每个时间步需要大量的优化运行，尤其是在状态和动作空间较大时，这些方法在计算上效率较低。为了解决这一问题，本文提出通过值偏置最大似然估计（VBMLE）来求解线性MDP。我们正式证明了VBMLE具有$ ilde{O}(d ext{sqrt}(T))$的遗憾，并且在每个时间步只需解决一个优化问题，从而在计算上更为高效。仿真结果表明，VBMLE在经验遗憾和计算时间方面显著优于基准方法。

🔬 方法详解

问题定义：本文旨在解决线性马尔可夫决策过程中的计算效率问题。现有方法在每个时间步需要进行多次优化，导致计算开销大，尤其在状态和动作空间较大时尤为明显。

核心思路：论文提出的VBMLE方法通过值偏置的最大似然估计，简化了优化过程，只需在每个时间步解决一个优化问题，从而提高了计算效率。

技术框架：整体架构包括线性MDP的建模、特征映射的定义、VBMLE的实施以及遗憾分析。主要模块包括状态转移建模、优化算法和收敛性分析。

关键创新：VBMLE的主要创新在于其通过值偏置的方式实现了高效的最大似然估计，与传统方法相比，显著降低了计算复杂度。

关键设计：在设计中，VBMLE采用了低维特征映射来参数化转移概率，并通过构造超马丁格尔来分析收敛性，确保了算法的有效性和稳定性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，VBMLE在经验遗憾方面优于基准方法，遗憾值达到了$ ilde{O}(d ext{sqrt}(T))$，并且在计算时间上显著减少，展示了其在大规模线性MDP中的优越性。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能制造等需要实时决策的场景。通过提高线性MDP的计算效率，VBMLE能够在复杂环境中实现更快速的决策，具有重要的实际价值和未来影响。

📄 摘要（原文）

We consider the infinite-horizon linear Markov Decision Processes (MDPs), where the transition probabilities of the dynamic model can be linearly parameterized with the help of a predefined low-dimensional feature mapping. While the existing regression-based approaches have been theoretically shown to achieve nearly-optimal regret, they are computationally rather inefficient due to the need for a large number of optimization runs in each time step, especially when the state and action spaces are large. To address this issue, we propose to solve linear MDPs through the lens of Value-Biased Maximum Likelihood Estimation (VBMLE), which is a classic model-based exploration principle in the adaptive control literature for resolving the well-known closed-loop identification problem of Maximum Likelihood Estimation. We formally show that (i) VBMLE enjoys $\widetilde{O}(d\sqrt{T})$ regret, where $T$ is the time horizon and $d$ is the dimension of the model parameter, and (ii) VBMLE is computationally more efficient as it only requires solving one optimization problem in each time step. In our regret analysis, we offer a generic convergence result of MLE in linear MDPs through a novel supermartingale construct and uncover an interesting connection between linear MDPs and online learning, which could be of independent interest. Finally, the simulation results show that VBMLE significantly outperforms the benchmark method in terms of both empirical regret and computation time.