Offline-to-Online Learning in Linear Bandits

Technical Summary: Offline-to-Online Learning in Linear Bandits

Problem Statement
This paper addresses the problem of offline-to-online learning within the stochastic linear bandit setting. The scenario involves a learner who sequentially selects actions from a set $\mathcal{A} \subset \mathbb{R}^d$ to maximize cumulative rewards over a horizon $n$, while having access to a pre-existing offline dataset $\mathcal{D}$. The offline data is collected via a fixed, non-adaptive design (deterministic action counts) and follows a linear reward model with subgaussian noise.

The core challenge lies in the tradeoff between two competing objectives:

1. Online Regret ($R_n$): Minimizing regret relative to the optimal action $\mu^*$. Standard online algorithms (e.g., LinUCB) rely on optimism to explore, achieving sublinear regret but potentially suffering high initial regret if the offline data is ignored.
2. Offline Regret ($R_n^{off}$): Minimizing regret relative to the mean reward of the offline dataset ($\mu_{off}$). Standard offline algorithms (e.g., LinLCB) rely on pessimism to exploit the known data, ensuring performance close to $\mu_{off}$ but failing to explore, which leads to linear regret if the offline data is suboptimal or if the horizon is long.

Existing work has largely treated these regimes separately or focused on multi-armed bandits (MAB) where regret scales with the number of actions. This paper seeks to bridge the gap in structured (linear) environments, where regret should scale with the dimension $d$ rather than the action space size.

Methodology: The LinOtO Algorithm
The authors propose LinOtO (Linear Offline-to-Online), an algorithm that dynamically balances exploration and exploitation by managing an exploration budget. The algorithm operates by switching between two strategies based on a confidence set $C_t$ constructed from both offline and online data:

1. Confidence Sets: The algorithm maintains a least-squares estimator $\hat{\theta}_t$ and a confidence ellipsoid $C_t$ around the true parameter $\theta^*$. The radius of this set incorporates uncertainty from both the offline data ($\beta_{off}$) and the online interactions ($\beta_t$).
2. Optimistic vs. Pessimistic Actions:
   • UCB Action ($U_t$): The action maximizing the Upper Confidence Bound within $C_t$. This promotes exploration and reduces $R_n$ but risks increasing $R_n^{off}$.
   • LCB Action ($L_t$): The action maximizing the Lower Confidence Bound (specifically, the maximum of the minimum confidence bounds over time). This promotes exploitation of the offline data, reducing $R_n^{off}$ but potentially increasing $R_n$.
3. Budget Mechanism:
   • The algorithm defines a safe baseline reward $r_b$, derived from a lower bound on the reward of a specific "safe" action $L_{off}$ (the LCB action computed solely from offline data). Proposition 2 guarantees that $L_{off}$ is close to $\mu_{off}$ with high probability.
   • An exploration budget $B(t)$ is maintained, representing the cumulative excess reward of the algorithm over the baseline $r_b$.
   • Decision Rule: If $B(t) > 0$, the algorithm selects the optimistic action $U_t$ (exploration). If $B(t) \le 0$, it selects the pessimistic action $L_t$ (exploitation) to accumulate budget.
   • This mechanism ensures that the algorithm only explores when it has "earned" the right to do so by staying safe relative to the offline baseline.

Key Contributions

1. Algorithm Design: The paper presents LinOtO, the first algorithm specifically designed for the offline-to-online linear bandit setting that simultaneously balances UCB and LCB strategies via a budget-based switching mechanism.
2. Theoretical Guarantees: The authors establish high-probability regret bounds for both metrics:
   • Online Regret ($R_n$): Theorem 1 shows that LinOtO achieves sublinear regret relative to the optimal action. The bound consists of a term dependent on the horizon $n$ (similar to LinUCB) and an additive constant dependent on the offline data quality. If the offline data covers the space well, the bound improves.
   • Offline Regret ($R_n^{off}$): Theorem 2 demonstrates that the regret relative to the offline reference scales linearly with $n$ but decreases as $O(1/\sqrt{m})$ with the number of offline samples $m$. This matches the performance of a purely offline (pessimistic) solution.
3. Pareto Tradeoff Analysis: The analysis reveals a tunable tradeoff controlled by a parameter $\alpha$. Increasing $\alpha$ favors online performance (closer to LinUCB), while decreasing $\alpha$ favors offline performance (closer to LinLCB).

Experimental Results
Empirical evaluations on synthetic linear bandit tasks (dimension $d=20$, $|A|=100$) demonstrate:

• Horizon Sensitivity: For short horizons, LinOtO tracks the conservative LinLCB baseline. For long horizons, it transitions to exploration, achieving sublinear regret comparable to LinUCB.
• Offline Data Quality:
  • When the offline dataset excludes the optimal action, LinOtO successfully deviates from the suboptimal offline prior to explore, eventually outperforming LinLCB (which suffers linear regret) and approaching LinUCB performance as offline data size $m$ increases.
  • When the offline dataset includes the optimal action, LinOtO converges rapidly, performing comparably to LinUCB and LinLCB.
• Robustness: The algorithm consistently performs between the extremes of pure exploration (LinUCB) and pure exploitation (LinLCB), adapting to the problem parameters.

Significance and Claims
The paper claims that LinOtO effectively resolves the "poorly understood" offline-to-online tradeoff in structured environments. Unlike prior work in MAB settings (e.g., Sentenac et al., 2025), this approach leverages the linear structure to ensure regret scales with dimension $d$ rather than the number of actions, making it scalable for high-dimensional problems.

The authors modestly note that their framework currently assumes fixed-design offline data and does not account for distribution shifts between offline and online data or adaptive logging policies. They identify addressing these limitations, along with extending the framework to nonlinear settings, as important directions for future research. The work contributes to the broader literature on leveraging prior knowledge (hints, offline data) to guide exploration-exploitation tradeoffs in online learning.