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:
- Statistical Efficiency (Regret): The agent must learn quickly from few samples to minimize "regret"—the gap between its performance and the optimal strategy.
- 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.
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