Short-Term Pain for Long-Term Gain: Adaptive Experiment with Post-Commitment Reward Shift

• URL: http://arxiv.org/abs/2607.23432v1
• Date: Sun, 26 Jul 2026 03:03:08 GMT
• Title: Short-Term Pain for Long-Term Gain: Adaptive Experiment with Post-Commitment Reward Shift
• Abstract summary: Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most.<n>To understand the tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts.
• Score: 7.0306572851625
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most. To understand the fundamental tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts. During an experiment phase, the decision-maker may adaptively test multiple options; during a subsequent commitment phase, the decision-maker must commit to a single option, whose reward may differ from its pre-commitment reward. We propose the Reserved Arm Eliminations for Commitment (RAEC) algorithm, which reserves a predetermined portion of the experiment phase to identify the best post-shift option while using the remaining rounds to minimize short-run regret. We establish regret upper bounds for RAEC across all parameter regimes and matching minimax lower bounds, providing a tight characterization of the cost of balancing short-term performance and long-term commitment. We also study two extensions. With prior structural knowledge linking pre- and post-shift rewards, we show that correctly identifying the ranking-changing component of the shift is more important than estimating its absolute magnitude. For settings with concave commitment rewards and portfolio choice, we develop the Reserved Online Stochastic Convex Optimization for Commitment (ROSCOC) algorithm, which directly converts its reserved exploration history into a commitment portfolio and achieves tight regret bound. Finally, we also conduct numerical experiments which confirm that our proposed algorithms achieve the desired regret predicted by our theory, and also outperform other baseline algorithms.

Related papers

• Efficient Online Conformal Selection with Limited Feedback [14.326282143930769]
  We address the problem of conformal selection, where an agent must select a minimal subset of options to ensure that at least one success'' is identified.<n>We show that the simple Adaptive Conformal Inference (ACI) update rule, when applied to the appropriate control parameter or dual variable, is both adversarially valid and efficient.
  arXiv  Detail & Related papers  (2026-05-14T15:22:46Z)
• ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
  We present ZIP-RC, an adaptive inference method that equips models with zero-overhead inference-time predictions of reward and cost.<n> ZIP-RC improves accuracy by up to 12% over majority voting at equal or lower average cost.
  arXiv  Detail & Related papers  (2025-12-01T09:44:31Z)
• Cascading Bandits With Feedback [4.305007244430146]
  We study a variant of the cascade bandit model in which each arm corresponds to an inference model with an associated accuracy and error probability.<n>We analyse four decision-making policies-Explore-then-Commit, Action Elimination, Lower Confidence Bound (LCB), and Thompson Sampling-and provide sharp theoretical regret guarantees for each.
  arXiv  Detail & Related papers  (2025-11-14T03:55:22Z)
• Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics [21.224078346005655]
  We study a nonstationary bandit problem where rewards depend on both actions and latent states.<n>We propose an explore-then-commit algorithm for a finite horizon $T$.<n>Our proposed algorithm achieves $tildemathcalO(T2/3)$ regret.
  arXiv  Detail & Related papers  (2025-10-17T20:41:14Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making.<n>We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss.<n>On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  We propose an algorithm called Mild-OGD for the full-information case, where delayed gradients are available.<n>We show that the dynamic regret of Mild-OGD can be automatically bounded by $O(sqrtbardT(P_T+1))$ under the in-order assumption.<n>We also develop a bandit variant of Mild-OGD for a more challenging case with only delayed loss values.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
  Reward-Biased Maximum Likelihood Estimate (RBMLE) for adaptive control of Markov chains was proposed. We show that it has a regret of $mathcalO( log T)$ over a time horizon of $T$ steps, similar to state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-11-16T06:09:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.