Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
复制标题
DOI：
10.48550/arxiv.2205.15512
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Wei Xiong;Han Zhong;Chengshuai Shi;Cong Shen;Liwei Wang;T. Zhang
中科院分区：
文献类型：
--
作者：
Wei Xiong;Han Zhong;Chengshuai Shi;Cong Shen;Liwei Wang;T. Zhang
离线强化学习（RL）旨在使用预先收集的数据集学习最佳策略，而无需与环境进一步交互。虽然之前的文献中已经针对离线强化学习提出了各种算法，但仅（几乎）为表格马尔可夫决策过程 (MDP) 建立了极小极大最优性。在本文中，我们专注于具有线性函数逼近的离线强化学习，并提出了一种新的基于悲观主义的离线线性 MDP 算法。我们算法的核心是通过参考函数进行不确定性分解，这在线性函数逼近下的离线强化学习文献中是新的。理论分析表明，我们的算法可以将性能下限与对数因子相匹配。我们还将我们的技术扩展到两人零和马尔可夫游戏（MG），并为 MG 建立了新的性能下界，这收紧了现有结果，并验证了所提出算法的近极小极大最优性。据我们所知，这些是第一个计算效率高且接近极小极大最优算法，适用于具有线性函数逼近的离线单智能体 MDP 和 MG。
Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the previous literature, the minimax optimality has only been (nearly) established for tabular Markov decision processes (MDPs). In this paper, we focus on offline RL with linear function approximation and propose a new pessimism-based algorithm for offline linear MDP. At the core of our algorithm is the uncertainty decomposition via a reference function, which is new in the literature of offline RL under linear function approximation. Theoretical analysis demonstrates that our algorithm can match the performance lower bound up to logarithmic factors. We also extend our techniques to the two-player zero-sum Markov games (MGs), and establish a new performance lower bound for MGs, which tightens the existing result, and verifies the nearly minimax optimality of the proposed algorithm. To the best of our knowledge, these are the first computationally efficient and nearly minimax optimal algorithms for offline single-agent MDPs and MGs with linear function approximation.