Technical Summary: One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RL

1. Problem Statement

The paper addresses the challenge of online transfer reinforcement learning (RL) in episodic Markov Decision Processes (MDPs). The setting involves a learner interacting with a target task ($M^{(0)}$) while having access to experience from related source tasks ($M^{(m)}$). The goal is to leverage source data to accelerate learning on the target task without compromising exploration or regret guarantees.

A fundamental obstacle identified is the misalignment between task similarity definitions and online RL learning mechanisms:

• Task Similarity: Typically defined via rewards, transitions, or value functions.
• RL Learning Mechanism: Modern online RL algorithms (e.g., Q-learning) operate by regressing one-step Bellman targets, which depend jointly on the continuation value ($V_{h+1}$) and the transition distribution ($P_h$).

The authors argue that naïve pooling of Bellman updates from source tasks introduces systematic bias. Even if tasks are intrinsically close, replacing the target continuation value $V^{(0)}_{h+1}$ with a source value $V^{(m)}_{h+1}$ or using source transition distributions $P^{(m)}_h$ creates a discrepancy that depends on the iteration-varying value function. This structural bias breaks optimism-based exploration and invalidates standard regret guarantees, as the error does not vanish with additional target data.

2. Methodology: Re-Weighted Targeting (RWT)

To resolve the structural bias, the paper proposes Re-Weighted Targeting (RWT), an operator-level correction that aligns Bellman operators across tasks.

2.1 One-Step Bellman Alignment

The core insight is that the Bellman mismatch between tasks can be reduced to a fixed one-step correction if the continuation value is evaluated under the target task while the transition mismatch is corrected via a change of measure.

Given a source task $m$ and target task $0$, let $\omega^{(m)}_h(s' | s, a) = p^{(0)}_h(s' | s, a) / p^{(m)}_h(s' | s, a)$ be the density ratio. The RWT-aligned Bellman operator is defined as:
$$(B^{(m \to 0)}_h V^{(m)}_{h+1})(s, a) := R^{(m)}_h(s, a) + \gamma \mathbb{E}_{s' \sim P^{(m)}_h} \left[ \omega^{(m)}_h(s' | s, a) V^{(0)}_{h+1}(s') \right]$$
Crucially, the continuation value $V^{(0)}_{h+1}$ is the target value function. The difference between the true target Bellman operator and the RWT-aligned source operator simplifies to:
$$\Delta^{(m)}_h(s, a) = (B^{(0)}_h V^{(0)}_{h+1})(s, a) - (B^{(m \to 0)}_h V^{(m)}_{h+1})(s, a) = R^{(0)}_h(s, a) - R^{(m)}_h(s, a)$$
This result shows that the task mismatch becomes a fixed one-step reward difference $\Delta^{(m)}_r$, independent of the value function $V_{h+1}$. This transforms the transfer problem into learning a structured residual rather than a complex, iteration-dependent bias.

2.2 Algorithmic Framework: RWT Q-Learning

The authors propose a two-stage RWT Q-learning framework (Algorithm 1) that separates variance reduction from bias correction:

1. Stage I: Source-Based Baseline (Variance Reduction)
   • Construct RWT-aligned pseudo-labels from source data using the current target value estimate $V_{h+1}$.
   • Fit a baseline estimator $Q^{base}_{n,h}$ using these pseudo-labels. This leverages abundant source data to reduce estimation variance while maintaining Bellman consistency with the target task up to the reward difference.
2. Stage II: Target-Based Correction (Bias Correction)
   • Compute residual labels using target data: $z_{i,h} = y^{(0)}_{i,h} - Q^{base}_{n,h}(s_{i,h}, a_{i,h})$.
   • Estimate a correction term $\delta_{n,h}$ to capture the structured one-step reward difference $\Delta^{(m)}_r$.
   • The final transfer estimate is $Q^{trans}_{n,h} = Q^{base}_{n,h} + \delta_{n,h}$.
3. Exploration:
   • An exploration bonus $b_{n,h}$ is added to $Q^{trans}_{n,h}$ to form an optimistic estimate $Q^{ucb}_{n,h}$, accounting for uncertainty from both the source baseline (including density ratio estimation) and the target correction.

2.3 Theoretical Instantiation (RKHS)

The framework is instantiated under Reproducing Kernel Hilbert Space (RKHS) function approximation:

• The target Bellman backup is assumed to lie in a high-complexity RKHS $\mathcal{K}$.
• The task shift (the reward difference $\Delta^{(m)}_r$) is assumed to lie in a lower-complexity RKHS $\tilde{\mathcal{K}} \subseteq \mathcal{K}$.
• Kernel ridge regression is used for both the baseline and the correction stages.
• Exploration bonuses are derived based on the information gain and covering numbers of the respective kernels.

3. Key Contributions

1. Conceptual: Identification of one-step Bellman alignment as the correct abstraction for online transfer. The paper demonstrates that naïve Bellman reuse is structurally biased due to continuation-value dependence, rendering it incompatible with regret guarantees.
2. Algorithmic: Proposal of Re-Weighted Targeting (RWT), an operator-level correction that enables statistically sound reuse of source data. This yields a two-stage Q-learning framework that decouples variance reduction (source) from bias correction (target).
3. Theoretical: Establishment of regret bounds under RKHS approximation that scale with the complexity of the task shift (the reward difference) rather than the complexity of the full target MDP. This provides strict improvements over single-task learning when the shift is structured.
4. Empirical: Demonstration of consistent improvements over single-task learning and naïve pooling in both tabular and neural network settings, validating the theoretical necessity of Bellman alignment.

4. Results

Theoretical Results

Under the assumption that the task shift lies in a lower-complexity RKHS $\tilde{\mathcal{K}}$, the regret bound for the OFU-RWT algorithm is:
$$\text{Regret}(N) \lesssim H \sqrt{N \beta_1} \left( N^{\beta_1+1} + N^{\alpha_1+1} \right) + \text{Source Terms}$$

• The dominant term depends on the complexity of the task shift ($\tilde{\mathcal{K}}$), not the ambient target MDP ($\mathcal{K}$).
• When the shift is simpler than the ambient problem (e.g., $\alpha_1 \leq \beta_1$), the regret is strictly lower than the $O(H N^{1/2+\beta_0})$ rate of single-task learning.
• The source estimation term decreases as the source-to-target sampling ratio $\kappa$ increases.

Empirical Results

Experiments were conducted on RandomRewardGridEnv, where the target reward is a fixed Q-table and the source reward is a perturbed version ($R_{source} = R_{target} + \Delta$).

• Naïve Pooling: Consistently degraded performance compared to target-only learning, confirming the structural bias predicted by theory.
• RWT-Q: Outperformed both naïve pooling and target-only baselines in both tabular and Deep Q-Network (DQN) settings.
• Sample Efficiency: RWT-Q showed significant gains in sample efficiency, particularly when the reward shift was structured but non-trivial.

5. Significance and Claims

The paper claims that Bellman alignment is a model-agnostic transfer principle essential for online RL.

• Structural vs. Statistical: The failure of naïve transfer is identified as a structural issue (operator misalignment) rather than a statistical one (insufficient data).
• Decomposition: By reducing task mismatch to a fixed one-step correction, RWT allows the separation of learning into a source-driven variance reduction phase and a target-driven bias correction phase.
• Regret Guarantees: Unlike previous transfer methods that rely on shared representations or offline assumptions, this work provides provably efficient online transfer with regret bounds that adapt to the complexity of the shift rather than the task.
• Generality: The mechanism is independent of the specific exploration strategy (compatible with $\epsilon$-greedy or UCB) and function approximator (tabular or neural), making it a general principle for online RL transfer.