面对短期最优与长期收益的冲突,提出新算法平衡探索与承诺。
Short-Term Pain for Long-Term Gain: Adaptive Experiment with Post-Commitment Reward Shift
- 预留部分实验期识别最优后调整选项,其余时间最小化短期损失。
- 理论证明算法在所有参数下均达最优后悔上界,精准刻画权衡代价。
- 适用于需权衡短期表现与长期承诺的决策场景,如投资组合选择。
学习环境中的决策者常面临短期最优行为未必带来长期最大收益的困境。本文研究带有事后奖励调整的自适应实验问题:在实验阶段可动态测试多个选项,在随后的承诺阶段必须选定单一选项,其奖励可能在承诺后发生变化。提出保留臂淘汰法(RAEC),预留部分实验期以识别最优后移选项,其余轮次用于最小化短期遗憾。建立了RAEC在所有参数下的后悔上界,并给出了匹配的极小极大下界,实现了对短期性能与长期承诺之间权衡代价的紧致刻画。进一步研究两类扩展:若预知前后奖励间的结构关系,则识别奖励排序变化成分比估计绝对值更关键;在凹奖励和组合选择场景下,提出保留在线随机凸优化(ROSCOC)算法,直接将保留的探索历史转化为承诺组合,达到紧致后悔界。数值实验验证了理论预测的后悔性能,且优于基线算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。