Provably Efficient Lifelong Reinforcement Learning with Linear Representation

Sanae Amani, Lin Yang, Ching-An ChengICLR 2023 · OpenReview

TL;DR

This paper introduces UCBlvd (UCB Lifelong Value Distillation), the first reinforcement learning algorithm for lifelong settings that simultaneously achieves sublinear regret and a sublinear number of planning calls. By leveraging a novel "completeness" assumption and a value distillation process, the agent learns to internalize experiences into a multi-task policy, allowing it to solve an adversarial sequence of tasks without constant, expensive re-planning.

The Challenge of Lifelong Reinforcement Learning

In a "lifelong learning" scenario, an agent (such as a household robot) must solve a sequence of different tasks over its lifetime. Most existing reinforcement learning (RL) research assumes tasks are either identical or drawn from a simple, fixed distribution. In reality, tasks are often adversarial or adaptive: what an agent does now changes what it must do next.

Two major hurdles exist for such agents:

  1. Statistical Efficiency (Regret): The agent must learn quickly from few samples to minimize "regret"—the gap between its performance and the optimal strategy.
  2. Computational Efficiency (Planning): Planning is computationally expensive. If a robot has to run a full optimization routine every time it receives a new command, it becomes impractical for real-time interaction.

Previous provable methods either ignored the computational cost (planning for every single task) or made overly restrictive assumptions about the number of tasks.

Methodology: Linearly Parameterized Contextual MDPs

The authors frame the problem as a Linearly Parameterized Contextual Markov Decision Process (CMDP). They assume the environment's dynamics are constant, but the rewards change based on a "context" (the task description).

Key Innovations

  • The Completeness Assumption: To allow knowledge sharing across tasks, the authors introduce a new assumption ensuring that the optimal value functions for all possible tasks can be represented linearly. This "optimistic closure" allows the agent to learn a single multi-task policy rather than a library of individual ones.
  • UCB Lifelong Value Distillation (UCBlvd):
    • Independent Planning: The agent plans for a small set of "representative" tasks.
  • Value Distillation: It uses a Convex Quadratically Constrained Quadratic Program (QCQP) to "distill" these specific plans into a general, multi-task value function.
  • Doubling Schedule: To save time, the agent doesn't re-plan for every new task. It only triggers a new planning phase when it has gathered a "significant" amount of new information about the environment, measured by the growth of its "Gram matrix" (a mathematical way of tracking explored space).

Key Insights

  • Internalization is Key: The goal isn't just to solve the current task, but to "internalize" the experience so that the next task can be solved faster or even "zero-shot."
  • Sublinear Planning is Possible: By using a doubling schedule, the authors prove that as the agent lives longer, it needs to call its expensive planner less and less frequently—specifically, only $\mathcal{O}(\log K)$ times over $K$ episodes.
  • Linear Structure for Transfer: The linear representation isn't just a simplification; it provides a geometric structure that tells the agent which tasks are "representative" of the entire task space.

Key Results

  • Regret Bound: The algorithm achieves a regret bound of $\tilde{\mathcal{O}}(\sqrt{(d^3 + d'd)H^4K})$, where $d$ and $d'$ are feature dimensions, $H$ is the time horizon, and $K$ is the number of tasks. This means the agent's average performance converges toward the optimum.
  • Planning Efficiency: While the baseline algorithm requires $K$ planning calls (one per task), UCBlvd requires only $\mathcal{O}(dH \log K)$ calls.
  • Empirical Validation: As a theoretical work, the paper evaluates the algorithm on synthetic environments designed to test the mathematical bounds. In simulations, UCBlvd achieved nearly identical reward performance to a statistically efficient but computationally heavy baseline (Lifelong-LSVI), while drastically reducing the number of planning calls from 1,000 down to approximately 21.
Comparison of per-episode reward and planning calls between Lifelong LSVI and UCBlvd.

Limitations and Future Directions

  • Linearity Constraints: The current proof relies heavily on linear representations. While many deep RL features are approximately linear in their final layers, extending this to general non-linear function approximation (like deep neural networks) remains an open challenge.
  • Known Contexts: The model assumes the task context (the "command") is revealed to the agent. A more difficult and realistic setting would involve latent contexts, where the agent has to figure out what the task is just by observing rewards.
  • Fixed Dynamics: The paper assumes the physics of the world stay the same while only the goals change. Future work could explore "lifelong" changes in dynamics (e.g., a robot's joints wearing out over time).

Summary updated

Abstract

We theoretically study lifelong reinforcement learning (RL) with linear representation in a regret minimization setting. The goal of the agent is to learn a multi-task policy based on a linear representation while solving a sequence of tasks that may be adaptively chosen based on the agent's past behaviors. We frame the problem as a linearly parameterized contextual Markov decision process (MDP), where each task is specified by a context and the transition dynamics is context-independent, and we introduce a new completeness-style assumption on the representation which is sufficient to ensure the optimal multi-task policy is realizable under the linear representation. Under this assumption, we propose an algorithm, called UCB Lifelong Value Distillation (UCBlvd), that provably achieves sublinear regret for any sequence of tasks while using only sublinear planning calls. 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})$ using $\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 learn to internalize experiences into a multi-task policy and rapidly solve new tasks.
BibTeX
@inproceedings{amani2023provably,
  author = {Sanae Amani and Lin Yang and Ching-An Cheng},
  title = {{Provably Efficient Lifelong Reinforcement Learning with Linear Representation}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=Qd0p0bl-A9t},
}
Figure