提出高效算法求解线性可表示值函数的强化学习问题
Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
- 基于代价敏感分类预言机设计新算法，实现多项式样本与调用次数
- 在特征维数恒定时，计算成本远低于现有方法且不随时序指数增长
- 适用于大规模或无限状态动作空间的复杂环境，适合算法研究者
设计样本高效且计算可行的强化学习算法，在状态和动作空间巨大甚至无限的环境中尤为困难。本文针对状态-动作值函数对任意策略均关于给定特征映射为线性的马尔可夫决策过程（MDP），提出一种高效算法。该设定可建模无限状态与动作环境，严格推广经典线性MDP，且当前在在线访问环境下尚无计算高效的算法。我们引入的新算法可在多项式数量的回合与代价敏感分类（CSC）预言机调用下，找到近优策略。特别地，当特征维数为常数时，该CSC预言机可高效实现，显著优于现有方法——后者需解决具有时序长度变量的非凸问题，计算开销可能随时序呈指数增长。
原文摘要 · Abstract (English)
Designing sample-efficient and computationally feasible reinforcement learning (RL) algorithms is particularly challenging in environments with large or infinite state and action spaces. In this paper, we advance this effort by presenting an efficient algorithm for Markov Decision Processes (MDPs) where the state-action value function of any policy is linear in a given feature map. This challenging setting can model environments with infinite states and actions, strictly generalizes classic linear MDPs, and currently lacks a computationally efficient algorithm under online access to the MDP. Specifically, we introduce a new RL algorithm that efficiently finds a near-optimal policy in this setting, using a number of episodes and calls to a cost-sensitive classification (CSC) oracle that are both polynomial in the problem parameters. Notably, our CSC oracle can be efficiently implemented when the feature dimension is constant, representing a clear improvement over state-of-the-art methods, which require solving non-convex problems with horizon-many variables and can incur computational costs that are exponential in the horizon.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。