Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
具有生成模型的线性参数化马尔可夫决策过程的样本高效强化学习AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
本页为预印本版本；arXiv 收录、作者填写的期刊信息以及作者既有发表经历，都不单独证明本篇已接收。作者发表记录按 OpenAlex 身份与完整姓名、本站覆盖期刊 ISSN 及正式卷期核对，只展示已核实例，档案仍可能误合并。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要研究通用强化学习的样本复杂度，未明确涉及所列计量领域的具体对象。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
具有生成模型的线性参数化马尔可夫决策过程的样本高效强化学习
- 研究问题
- 当状态与动作空间很大、转移核可由低维特征线性表达或近似时，如何通过生成模型采样，以较少样本学习近似最优策略？
- 方法与思路
- 作者分析基于模型的方法与 Q-learning，在生成模型采样条件下，以特征维度、折扣因子和目标精度刻画高概率样本复杂度。
- 材料陈述的贡献
- 摘要称，两类方法的复杂度界均紧，基于模型的方法达到极小极大下界；所需样本量依赖特征维度，从而缓解状态动作规模问题。
- 阅读关注点
- 应核对生成模型的访问方式、特征与转移核约束，以及线性近似误差如何进入保证、对数项内容和上下界所覆盖的模型类。
- 阅读边界
- 这是 arXiv 预印本，同行评审与期刊接收未核实；摘要未说明完整模型条件和近似误差影响，结论不能直接外推至仅有离线轨迹的场景。
原文摘要
The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space $\mathcal{S}$ and the action space $\mathcal{A}$ are both finite, to obtain a nearly optimal policy with sampling access to a generative model, the minimax optimal sample complexity scales linearly with $|\mathcal{S}|\times|\mathcal{A}|$, which can be prohibitively large when $\mathcal{S}$ or $\mathcal{A}$ is large. This paper considers a Markov decision process (MDP) that admits a set of state-action features, which can linearly express (or approximate) its probability transition kernel. We show that a model-based approach (resp.$~$Q-learning) provably learns an $\varepsilon$-optimal policy (resp.$~$Q-function) with high probability as soon as the sample size exceeds the order of $\frac{K}{(1-γ)^{3}\varepsilon^{2}}$ (resp.$~$$\frac{K}{(1-γ)^{4}\varepsilon^{2}}$), up to some logarithmic factor. Here $K$ is the feature dimension and $γ\in(0,1)$ is the discount factor of the MDP. Both sample complexity bounds are provably tight, and our result for the model-based approach matches the minimax lower bound. Our results show that for arbitrarily large-scale MDP, both the model-based approach and Q-learning are sample-efficient when $K$ is relatively small, and hence the title of this paper.