提出高效算法解决线性马尔可夫决策过程的平均奖励问题。
A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs
- 通过只在访问过的状态上计算最小值，实现快速截断操作。
- 在不依赖状态空间大小的前提下，保持与先前方法相同的误差界。
- 适合大规模或无限状态空间的强化学习场景使用。
我们研究了在无限时域平均奖励设定下的线性马尔可夫决策过程（linear MDP）中的强化学习问题。以往工作通过将平均奖励设置近似为折扣设置，并采用基于价值迭代的算法，利用截断技术限制价值函数的跨度以提升统计效率。然而，该截断过程需要计算价值函数在整个状态空间上的最小值，这在状态空间大甚至无穷的情况下难以实现。本文提出一种新的价值迭代方法，其截断操作仅需在算法访问过的状态集合上计算最小值，从而显著降低计算开销。所提算法在保持与先前工作相同误差边界的同时，计算复杂度与状态空间规模无关，具有良好的可扩展性。
原文摘要 · Abstract (English)
We study reinforcement learning in infinite-horizon average-reward settings with linear MDPs. Previous work addresses this problem by approximating the average-reward setting by discounted setting and employing a value iteration-based algorithm that uses clipping to constrain the span of the value function for improved statistical efficiency. However, the clipping procedure requires computing the minimum of the value function over the entire state space, which is prohibitive since the state space in linear MDP setting can be large or even infinite. In this paper, we introduce a value iteration method with efficient clipping operation that only requires computing the minimum of value functions over the set of states visited by the algorithm. Our algorithm enjoys the same regret bound as the previous work while being computationally efficient, with computational complexity that is independent of the size of the state space.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。