# Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards

arXiv: https://arxiv.org/abs/1906.00569 · HTML: https://mlsanity.com/paper/1906.00569/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 19 of 19)

- [Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR](https://mlsanity.com/paper/2302.03201/) (2023)
- [Off-Policy Risk Assessment in Contextual Bandits](https://mlsanity.com/paper/2104.08977/) (2021)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Constrained Pure Exploration Multi-Armed Bandits with a Fixed Budget](https://mlsanity.com/paper/2211.14768/) (2022)
- [A Survey of Risk-Aware Multi-Armed Bandits](https://mlsanity.com/paper/2205.05843/) (2022)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Online Estimation and Optimization of Utility-Based Shortfall Risk](https://mlsanity.com/paper/2111.08805/) (2021)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [Bias-Corrected Peaks-Over-Threshold Estimation of the CVaR](https://mlsanity.com/paper/2103.05059/) (2021)
- [Sample-Based Bounds for Coherent Risk Measures: Applications to Policy Synthesis and Verification](https://mlsanity.com/paper/2204.09833/) (2022)
- [Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits](https://mlsanity.com/paper/2406.05710/) (2024)
- [Risk-sensitive Bandits: Arm Mixture Optimality and Regret-efficient Algorithms](https://mlsanity.com/paper/2503.08896/) (2025)
- [Continuous Mean-Covariance Bandits](https://mlsanity.com/paper/2102.12090/) (2021)
- [Risk-Aware Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2112.01141/) (2021)
- [Concentration Bounds for Optimized Certainty Equivalent Risk Estimation](https://mlsanity.com/paper/2405.20933/) (2024)
- [Optimizing Sharpe Ratio: Risk-Adjusted Decision-Making in Multi-Armed Bandits](https://mlsanity.com/paper/2406.06552/) (2024)
- [Variance-Optimal Arm Selection: Misallocation Minimization and Best Arm Identification](https://mlsanity.com/paper/2505.11985/) (2025)
- [Concave Statistical Utility Maximization Bandits via Influence-Function Gradients](https://mlsanity.com/paper/2604.22140/) (2026)

## Abstract (arXiv)

Classical multi-armed bandit problems use the expected value of an arm as a metric to evaluate its goodness. However, the expected value is a risk-neutral metric. In many applications like finance, one is interested in balancing the expected return of an arm (or portfolio) with the risk associated with that return. In this paper, we consider the problem of selecting the arm that optimizes a linear combination of the expected reward and the associated Conditional Value at Risk (CVaR) in a fixed budget best-arm identification framework. We allow the reward distributions to be unbounded or even heavy-tailed. For this problem, our goal is to devise algorithms that are entirely distribution oblivious, i.e., the algorithm is not aware of any information on the reward distributions, including bounds on the moments/tails, or the suboptimality gaps across arms. In this paper, we provide a class of such algorithms with provable upper bounds on the probability of incorrect identification. In the process, we develop a novel estimator for the CVaR of unbounded (including heavy-tailed) random variables and prove a concentration inequality for the same, which could be of independent interest. We also compare the error bounds for our distribution oblivious algorithms with those corresponding to standard non-oblivious algorithms. Finally, numerical experiments reveal that our algorithms perform competitively when compared with non-oblivious algorithms, suggesting that distribution obliviousness can be realised in practice without incurring a significant loss of performance.