arXiv:2501.10598cs.LG2025-01被引 1

用低秩张量近似有限时域强化学习中的价值函数,提升计算效率。

Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation

  • 将价值函数建模为低秩张量,降低高维状态空间复杂度
  • 提出基于块坐标下降的算法,理论保证收敛且减少计算开销
  • 适用于动态未知的资源分配等实际问题,性能优于传统方法

我们研究在有限时域马尔可夫决策过程(MDP)中,利用低秩强化学习方法学习最优策略。由于有限时域MDP中的策略和价值函数(VFs)不具平稳性,高维情形下面临维度灾难和高样本复杂度挑战。为此,本文将价值函数建模为低秩张量,实现可扩展表示,使最优策略学习成为可能。方法基于策略迭代框架,结合低秩策略评估与贪婪策略改进,求解近优策略。提出一种带低秩约束的贝尔曼方程优化框架,配套设计块坐标下降(BCD)与块坐标梯度下降(BCGD)算法,均具备理论收敛性。进一步证明:有界低秩策略评估误差可转化为有限时域设置下的有界策略改进。当系统动态未知时,通过采样轨迹适配所提BCGD方法估计价值函数。数值实验表明,该框架在受控合成场景与更真实的资源分配问题中显著降低计算需求,并在获得回报方面保持竞争力。

原文摘要 · Abstract (English)

We study the problem of learning optimal policies in finite-horizon Markov Decision Processes (MDPs) using low-rank reinforcement learning (RL) methods. In finite-horizon MDPs, the policies, and therefore the value functions (VFs) are not stationary. This aggravates the challenges of high-dimensional MDPs, as they suffer from the curse of dimensionality and high sample complexity. To address these issues, we propose modeling the VFs of finite-horizon MDPs as low-rank tensors, enabling a scalable representation that renders the problem of learning optimal policies tractable. Our approach focuses on VF approximation within a policy iteration framework, where low-rank policy evaluation is combined with greedy policy improvement to compute near-optimal policies. We introduce an optimization-based framework for solving the Bellman equations with low-rank constraints, along with block-coordinate descent (BCD) and block-coordinate gradient descent (BCGD) algorithms, both with theoretical convergence guarantees. We further establish that bounded low-rank policy evaluation error translates into bounded policy improvement in the finite-horizon setting. For scenarios where the system dynamics are unknown, we adapt the proposed BCGD method to estimate the VFs using sampled trajectories. Numerical experiments further demonstrate that the proposed framework reduces computational demands in controlled synthetic scenarios and more realistic resource allocation problems, while achieving competitive policy performance in terms of attained returns.

强化学习低秩逼近张量方法策略迭代

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。