Northwestern's O-O UCRL-VTR Turns Stale Biased Logs Into Faster RL
A new algorithm safely combines offline data with online exploration under environment shift, provably matching pure-online performance when historical data misleads.
ProTakeaways
- New algorithm O-O UCRL-VTR safely combines offline and online RL for linear mixture MDPs under environment shift.
- Uses two parameter estimators and takes the intersection of their confidence sets, defaulting to online-only when logs mislead.
- Regret bound has min-of-two structure, provably matched by nearly tight lower bounds in d, K, M_off, and delta.
- Offline data helps when coverage tau is large relative to K/M_off and shift delta scales linearly with tau.
- Pessimism-based offline estimation hurts here because offline-optimal and online-optimal policies can differ substantially.
- Code and simulations available at the GitHub repo.
Reinforcement learning has a well-known cold-start problem. When you launch a new product, deploy a new robot, or start treating a new patient population, you rarely have the luxury of a high-fidelity simulator to burn through millions of interactions. You do, however, often have logs from a related setting: sales histories from similar products, telemetry from an older robot, outcomes from a comparable patient cohort. The question is whether pulling in that stale, biased data actually helps, or quietly poisons the online learner.
A new paper from researchers at Northwestern University tackles this question for linear mixture Markov decision processes, a function-approximation setting general enough to subsume tabular MDPs and linear bandits. The authors propose an algorithm called O-O UCRL-VTR that provably improves over purely online learning when the offline data is informative, and gracefully falls back to online-only performance when it isn't.
When logs poison live data
Naively combining offline and online data without accounting for environment shift can introduce bias and lead to linear regret, the worst possible outcome in RL: regret that grows with every episode instead of shrinking. Two things make this hard.
- Offline data may be generated under a similar but not identical environment, leading to bias under environment shift. Historical demand for an existing product is not the demand for a new one.
- The offline data is collected under a behavior policy, which shapes the observed logs in ways that may not align with the target objective. If the logging policy avoided certain actions, the data tells you almost nothing about them.
Prior work sidesteps these problems by assuming them away. Some papers assume no environment shift; others impose restrictive conditions on the offline behavior policy, such as fixed sampling in bandits or uniform visitation in tabular MDPs. None of that scales to large or continuous state-action spaces.