A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits

• URL: http://arxiv.org/abs/2206.02969v6
• Date: Mon, 22 Jul 2024 14:45:09 GMT
• Title: A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits
• Authors: David Simchi-Levi, Zeyu Zheng, Feng Zhu,
• Abstract summary: We study the multi-armed bandit problem and design new policies that enjoy both worst-case optimality for expected regret and light-tailed risk for regret distribution. We find that from a managerial perspective, our new policy design yields better tail distributions and is preferable than celebrated policies.
• Score: 27.058087400790555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the stochastic multi-armed bandit problem and design new policies that enjoy both worst-case optimality for expected regret and light-tailed risk for regret distribution. Specifically, our policy design (i) enjoys the worst-case optimality for the expected regret at order $O(\sqrt{KT\ln T})$ and (ii) has the worst-case tail probability of incurring a regret larger than any $x>0$ being upper bounded by $\exp(-\Omega(x/\sqrt{KT}))$, a rate that we prove to be best achievable with respect to $T$ for all worst-case optimal policies. Our proposed policy achieves a delicate balance between doing more exploration at the beginning of the time horizon and doing more exploitation when approaching the end, compared to standard confidence-bound-based policies. We also enhance the policy design to accommodate the "any-time" setting where $T$ is unknown a priori, and prove equivalently desired policy performances as compared to the "fixed-time" setting with known $T$. Numerical experiments are conducted to illustrate the theoretical findings. We find that from a managerial perspective, our new policy design yields better tail distributions and is preferable than celebrated policies especially when (i) there is a risk of under-estimating the volatility profile, or (ii) there is a challenge of tuning policy hyper-parameters. We conclude by extending our proposed policy design to the stochastic linear bandit setting that leads to both worst-case optimality in terms of expected regret and light-tailed risk on the regret distribution.

Related papers

• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [63.32053223422317]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. In particular, we focus on characterizing the variance over values induced by a distribution over MDPs. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  We study the fixed-confidence best arm identification problem in the bandit framework. We propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule.
  arXiv  Detail & Related papers  (2023-10-01T01:37:02Z)
• Importance-Weighted Offline Learning Done Right [16.4989952150404]
  We study the problem of offline policy optimization in contextual bandit problems. The goal is to learn a near-optimal policy based on a dataset of decision data collected by a suboptimal behavior policy. We show that a simple alternative approach based on the "implicit exploration" estimator of citet2015 yields performance guarantees that are superior in nearly all possible terms to all previous results.
  arXiv  Detail & Related papers  (2023-09-27T16:42:10Z)
• Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk [22.843623578307707]
  We study the trade-off between expectation and tail risk for regret distribution in the multi-armed bandit problem. We show how the order of expected regret exactly affects the decaying rate of the regret tail probability for both the worst-case and instance-dependent scenario.
  arXiv  Detail & Related papers  (2023-04-10T01:00:18Z)
• Best of Both Worlds Policy Optimization [33.13041034490332]
  We show that by properly designing the regularizer, the exploration bonus and the learning rates, one can achieve a more favorable polylog$(T)$ regret when the losses are adversarial. This is the first time a gap-dependent polylog$(T)$ regret bound is shown for policy optimization.
  arXiv  Detail & Related papers  (2023-02-18T19:46:11Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  We propose an algorithm that minimizes the regret over the horizon of time $T$. The proposed algorithm is applicable to domains such as recommendation systems and transportation.
  arXiv  Detail & Related papers  (2023-01-31T03:49:00Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  We show that the preferability of optimization methods depends critically on whether exact gradients are used. Second, to explain these findings we introduce the concept of committal rate for policy optimization. Third, we show that in the absence of external oracle information, there is an inherent trade-off between exploiting geometry to accelerate convergence versus achieving optimality almost surely.
  arXiv  Detail & Related papers  (2021-10-29T06:35:44Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)

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.