Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximation

2022-06-01 · Sanae Amani, Lin F. Yang, Ching-An Cheng

We study lifelong reinforcement learning (RL) in a regret minimization setting of linear contextual Markov decision process (MDP), where the agent needs to learn a multi-task policy while solving a streaming sequence of tasks. We propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks, which may be adaptively chosen based on the agent's past behaviors. Remarkably, our algorithm uses only sublinear number of planning calls, which means that the agent eventually learns a policy that is near optimal for multiple tasks (seen or unseen) without the need of deliberate planning. A key to this property is a new structural assumption that enables computation sharing across tasks during exploration. Specifically, for $K$ task episodes of horizon $H$, our algorithm has a regret bound $\tilde{\mathcal{O}}(\sqrt{(d^3+d^\prime d)H^4K})$ based on $\mathcal{O}(dH\log(K))$ number of planning calls, where $d$ and $d^\prime$ are the feature dimensions of the dynamics and rewards, respectively. This theoretical guarantee implies that our algorithm can enable a lifelong learning agent to accumulate experiences and learn to rapidly solve new tasks.

📄 PDF Abstract BibTeX arXiv:2206.00270

Code (0)

등록된 구현이 없습니다.

Tasks

4kLifelong learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle

2019-12-01 · NeurIPS 2019 12 · Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang

Q-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, ap…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle

2019-06-14 · Simon S. Du, Yuping Luo, Ruosong Wang, Hanrui Zhang

$Q$-learning with function approximation is one of the most popular methods in reinforcement learning. Though the idea of using function approximation was proposed at least 60 years ago, even in the simplest setup, i.e, …

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension

2020-05-21 · NeurIPS 2020 12 · Ruosong Wang, Ruslan Salakhutdinov, Lin F. Yang

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation…

Reinforcement Learning (RL)

Provably Efficient Reinforcement Learning with Linear Function Approximation

2019-07-11 · Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael. I. Jordan

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The in…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Optimism in Reinforcement Learning with Generalized Linear Function Approximation

2019-12-09 · ICLR 2021 1 · Yining Wang, Ruosong Wang, Simon S. Du, Akshay Krishnamurthy

We design a new provably efficient algorithm for episodic reinforcement learning with generalized linear function approximation. We analyze the algorithm under a new expressivity assumption that we call "optimistic closu…