Technical Summary: Adaptive Experiment with Post-Commitment Reward Shift

1. Problem Formulation

The paper addresses a sequential decision-making dilemma faced by decision-makers in learning environments where short-term optimal actions may conflict with long-term benefits due to an anticipated environmental shift. The problem is modeled as a two-phase adaptive experiment with $T$ total periods and $K$ candidate treatments (arms).

• Phase 1: Experiment Phase (Rounds $1$ to $N$): The decision-maker can adaptively select different arms to observe random outcomes. The reward function during this phase is $f(\cdot)$. The budget $N$ is exogenously determined (e.g., by a regulatory grace period).
• Phase 2: Commitment Phase (Rounds $N+1$ to $T$): The decision-maker must commit to a single arm (in the baseline model) and implement it for the remaining $T-N$ rounds. Crucially, the reward function shifts to $g(\cdot)$, which may differ from $f(\cdot)$. Consequently, the arm optimal for $f$ may be suboptimal for $g$.

The objective is to maximize the cumulative expected reward across both phases. The performance is measured by Regret, defined as the difference between the total reward of an optimal clairvoyant strategy (which knows the optimal arms for both $f$ and $g$ in advance) and the reward achieved by the online learning algorithm.

The core challenge is the trade-off: allocating too much exploration to the short-term reward $f$ risks selecting a poor arm for the long-term commitment $g$, while over-investing in identifying the optimal $g$-arm incurs excessive short-term regret.

2. Methodology: The RAEC Algorithm

The authors propose the Reserved Arm Eliminations for Commitment (RAEC) algorithm. Unlike standard multi-armed bandit (MAB) algorithms that adaptively balance exploration and exploitation, RAEC employs a predetermined allocation strategy.

• Structure: The algorithm operates in the experiment phase ($N$ rounds) via two stages, followed by a commitment stage.
  • Stage I (Reserved Exploration): A predetermined number of epochs ($L$) are reserved exclusively to eliminate suboptimal arms with respect to the commitment-phase reward function $g$. The algorithm uses hypothesis tests to eliminate arms that perform poorly under $g$, ensuring the final commitment set contains the best $g$-arm with high probability.
  • Stage II (Regret Minimization): The remaining rounds in the experiment phase are used to minimize regret with respect to the experiment-phase reward function $f$, using standard arm elimination techniques.
  • Commitment Stage: At round $N+1$, the algorithm commits uniformly at random to one of the surviving arms from the Stage I set.
• Key Design Feature: The algorithm does not adaptively learn the instance structure to decide how much to explore for $g$. Instead, it fixes the effort allocation based on the parameters $N$, $T$, and $K$. This "reserved" approach simplifies implementation and provides transparency regarding the effort devoted to long-term gains.

3. Key Contributions and Results

A. Regret Upper Bounds

The paper establishes tight regret upper bounds for RAEC across all parameter regimes defined by the relationship between the experiment budget $N$, the commitment horizon $T-N$, and the number of arms $K$. The regret bounds exhibit a phase transition:

1. Short Experiment Regime ($N \lesssim K^{1/3}(T-N)^{2/3}$): The experiment phase is too short to balance both objectives. The optimal strategy focuses on pure exploration for $g$.
   • Regret: $\tilde{O}\left(\sqrt{\frac{KT^2}{N}}\right)$.
2. Balanced Regime ($N \gtrsim K^{1/3}(T-N)^{2/3}$ and $T-N \gtrsim K^{1/4}T^{3/4}$): Both phases are significant. The algorithm balances exploration for $g$ and exploitation for $f$.
   • Regret: $\tilde{O}\left(K^{1/3}(T-N)^{2/3}\right)$.
3. Short Commitment Regime ($T-N \lesssim K^{1/4}T^{3/4}$): The commitment phase is short, resembling a standard MAB problem where short-term regret dominates.
   • Regret: $\tilde{O}\left(\sqrt{KT}\right)$.

B. Information-Theoretic Lower Bounds

The authors prove matching minimax lower bounds for any consistent policy. This confirms that RAEC achieves the optimal regret rate (up to logarithmic factors) and that the "predetermined" allocation strategy is sufficient; more sophisticated adaptive methods that learn the instance structure do not improve the leading order of the regret.

C. Extensions

The paper analyzes two extensions:

1. Structural Knowledge of Reward Shifts: If the decision-maker knows the functional relationship between $f$ and $g$ (e.g., a perturbed affine relationship), the paper shows that correctly identifying the ranking-changing component of the shift is far more critical than estimating the absolute magnitude of the shift. If the shift preserves rankings, regret performance improves significantly.
2. Concave Commitment Rewards (Portfolio Choice): In settings where the commitment reward is a concave function of the portfolio's aggregate outcome (e.g., balancing profit and environmental impact), the authors propose the Reserved Online Stochastic Convex Optimization for Commitment (ROSCOC) algorithm. Instead of eliminating arms, ROSCOC uses online stochastic convex optimization during the reserved phase and commits to the empirical distribution of the execution path. It achieves regret bounds comparable to the baseline RAEC.

4. Numerical Experiments

The authors conduct numerical experiments to validate their theoretical findings:

• Scaling Verification: Experiments confirm that the empirical regret of RAEC scales with $T$ according to the predicted theoretical slopes (e.g., $T^{3/4}$, $T^{2/3}$, $T^{1/2}$) across different commitment schedules.
• Baseline Comparison: RAEC is compared against a UCB-style baseline that optimizes for short-term reward $f$ and only selects the best $g$-arm at the end. In balanced regimes, RAEC outperforms the UCB baseline in the long run. The UCB baseline fails to allocate sufficient samples to distinguish between arms that are suboptimal for $f$ but optimal for $g$, leading to costly commitment errors.
• Concave Extension: Similar results are observed for ROSCOC compared to a UCB-Portfolio baseline, demonstrating that reserving exploration for the long-term objective yields superior long-horizon performance even in non-linear settings.

5. Significance and Claims

The paper claims to provide a tight characterization of the cost of balancing short-term performance and long-term commitment in the presence of reward shifts.

• Fundamental Trade-off: The work highlights that the presence of a post-commitment reward shift fundamentally alters the difficulty of the problem compared to standard MABs, often resulting in higher regret rates (e.g., $T^{2/3}$ vs. $T^{1/2}$) in balanced regimes.
• Sufficiency of Simple Strategies: A central implication is that predetermined effort allocation is sufficient to achieve minimax optimality. Decision-makers do not need complex adaptive mechanisms to learn the instance structure to determine how much to explore for the future; a simple, pre-calculated reservation of resources is optimal.
• Managerial Insight: The results offer quantitative guidance for practitioners (e.g., in platform regulation or supply chain management) on how much capacity to reserve for experimentation versus immediate operations when anticipating policy or environmental shifts. Specifically, it clarifies that identifying the ranking of options under the new environment is more critical than the precise magnitude of the reward shift.

The paper concludes that while the problem is more challenging than standard bandit problems due to the reward shift, the proposed algorithms (RAEC and ROSCOC) effectively manage this trade-off with provable guarantees.