线性马尔科夫决策过程(MDP)中的特征选择和零稀疏线性 MDP,以及通过凸规划有效计算的模拟器、低深度决策树上的区块 MDP 的学习算法。
Sep, 2023
提出在给定特征空间中嵌入转移函数的二人零和随机博弈中,通过采样逼近纳什均衡策略的二人 Q-learning 算法,已证明可使用与特征数线性相关的样本大小找到 ε 最优策略;进一步改进算法的样本效率,采用方差约减、单调性保持和双侧策略逼近等技术来加速算法,证明了该算法最多只需要使用 O~(K/(ε^2 (1-γ)^4)) 个样本即可以高概率找到 ε 最优策略,其中 K 是特征数,γ 是折扣系数;算法的样本、时间和空间复杂度与游戏的原始维度无关。
Jun, 2019
该论文研究利用最近邻回归方法的最近邻 Q 学习算法,从单一样本路径中学习具有连续状态空间和未知转移核的无限期贴现 MDPs 的最优 Q 函数,提供了紧密的有限样本收敛速率分析和样本复杂度。
Feb, 2018
本文论述了基于核心回归的 Q 学习在存在生成模型时的采样复杂度,提出了一种非参数 Q 学习算法,其样本复杂度优化到 ε 和核心复杂度的阶数,这是针对这种普遍模型的首个具有有限样本复杂度的结果。
Feb, 2023
本文研究了基于模型的强化学习的样本复杂度问题,通过插件求解器方法,在马尔科夫决策过程中找到了一种可以降低样本复杂度的方式,并证明了此方法的最小化样本复杂度是 O (K/(1-gamma)^3*epsilon^2),从而提供了为基于模型的 RL 设计算法的灵活方法。
Oct, 2020
本文提出了一种无模型的算法来学习具有折扣因子的马尔可夫决策过程中的政策,该算法的成功概率为 (1-p),且具有样本复杂度 O (SALn (1/p)/(ε^2 (1-γ)^3)),其中 S 是状态数,A 是行动数,γ 是折扣因子,ε 是一个近似阈值
Jun, 2020
本文介绍了一种基于 Approximate linear programming (APL) 的算法 ——bilinear pi learning,在采样 oracle 下用于强化学习,并证明了它具有可扩展性、在线实时性和样本效率等多种优势。
Apr, 2018
本文研究了在具有线性函数逼近和生成模型的固定时间段和折扣式马尔可夫决策过程中的本地规划问题,并结合限制的特征映射来回答是否存在只需多项式数量查询的可靠规划器的问题,并提出了最小二乘值迭代算法用于计算优化方案。
学习连续空间马尔可夫决策过程中的 ε- 最优策略问题,在具有光滑 Bellman 算子的一般类别中,通过使用正交三角多项式特征的简单的扰动最小二乘值迭代,并结合基于谐波分析的新型投影技术,实现了速率最优的样本复杂性。
May, 2024
提出一种新的随机线性规划算法,利用价值 - 策略对偶和二叉树数据结构,自适应地采样状态 - 动作 - 状态转移,并进行指数原始 - 对偶更新,从而以几乎线性的运行时间在最坏情况下找到一个 ε- 最优策略。当马尔可夫决策过程是遍历的并且以某些特殊的数据格式指定时,该算法使用线性的运行时间,在状态 - 动作对的总数中是次线性的,为解决随机动态规划问题提供了新的途径和复杂性基准。
Apr, 2017