标题： 告别武器：在预算内带有放弃选项的顺序奖励最大化 显示英文标题

标题： A Farewell to Arms: Sequential Reward Maximization on a Budget with a Giving Up Option

摘要： 我们考虑一个顺序决策问题，其中代理一次只能执行一个动作，每个动作都有一个随机的时间跨度，即在前一个动作完成之前不能执行新动作。 完成后，所选动作会带来一个随机奖励。 代理的目标是在有限的时间预算内最大化其累积奖励，并可以选择“放弃”当前动作——从而放弃任何奖励——以选择另一个动作。 我们将这个问题视为一种具有随机资源消耗的随机多臂老虎机问题。 对于这个问题，我们首先确定最优的臂是那个使臂的期望奖励与由于拉动该臂而使代理看到奖励之前的期望等待时间之比最大的臂。 使用这个比值的新颖上界，我们引入了一个基于上界置信度的算法 WAIT-UCB，我们建立了对该算法的对数问题依赖性遗憾边界，与之前的工作相比，其对问题参数的依赖性有所改进。 还展示了在各种问题配置上的模拟结果，将 WAIT-UCB 与最先进的算法进行了比较。 显示英文摘要

摘要： We consider a sequential decision-making problem where an agent can take one action at a time and each action has a stochastic temporal extent, i.e., a new action cannot be taken until the previous one is finished. Upon completion, the chosen action yields a stochastic reward. The agent seeks to maximize its cumulative reward over a finite time budget, with the option of "giving up" on a current action -- hence forfeiting any reward -- in order to choose another action. We cast this problem as a variant of the stochastic multi-armed bandits problem with stochastic consumption of resource. For this problem, we first establish that the optimal arm is the one that maximizes the ratio of the expected reward of the arm to the expected waiting time before the agent sees the reward due to pulling that arm. Using a novel upper confidence bound on this ratio, we then introduce an upper confidence based-algorithm, WAIT-UCB, for which we establish logarithmic, problem-dependent regret bound which has an improved dependence on problem parameters compared to previous works. Simulations on various problem configurations comparing WAIT-UCB against the state-of-the-art algorithms are also presented.