Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
复制标题
DOI：
10.48550/arxiv.2210.00701
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Dan Qiao;Yu-Xiang Wang
中科院分区：
文献类型：
--
作者：
Dan Qiao;Yu-Xiang Wang
研究了无奖励探索环境下线性函数逼近的部署有效强化学习问题.这是一个动机很好的问题，因为在现实生活中的RL应用程序中部署新策略是昂贵的。在线性MDP设置与特征维度$d$和规划视野$H$，我们提出了一个新的算法，收集最多$\widetilde{O}（\frac{d^2H^5}{\epsilon ^2}）$轨迹内$H$部署，以确定$\frac $-最优策略的任何（可能依赖于数据）的奖励函数的选择。据我们所知，我们的方法是第一个同时实现最优部署复杂度和样本复杂度的最优$d$依赖性的方法，即使提前知道回报。我们的新技术包括探索保持政策离散化和广义G-最优实验设计，这可能是独立的利益。最后，我们分析了低适应RL中遗憾最小化的相关问题，并给出了切换成本和批处理复杂度的信息论下界。
We study the problem of deployment efficient reinforcement learning (RL) with linear function approximation under the \emph{reward-free} exploration setting. This is a well-motivated problem because deploying new policies is costly in real-life RL applications. Under the linear MDP setting with feature dimension $d$ and planning horizon $H$, we propose a new algorithm that collects at most $\widetilde{O}(\frac{d^2H^5}{\epsilon^2})$ trajectories within $H$ deployments to identify $\epsilon$-optimal policy for any (possibly data-dependent) choice of reward functions. To the best of our knowledge, our approach is the first to achieve optimal deployment complexity and optimal $d$ dependence in sample complexity at the same time, even if the reward is known ahead of time. Our novel techniques include an exploration-preserving policy discretization and a generalized G-optimal experiment design, which could be of independent interest. Lastly, we analyze the related problem of regret minimization in low-adaptive RL and provide information-theoretic lower bounds for switching cost and batch complexity.