Distributionally-Aware Exploration for CVaR Bandits

Abstract¶

Risk sensitive objectives are often desirable in settings like healthcare or finance, where agents are more sensitive to worst-case than average outcomes. However, current risk-sensitive algorithms for multi-armed bandits utilize exploration bonuses which do not adapt to the distributional nature of these objectives. In this paper, we consider multi-armed bandits with a popular risk-sensitive objective called the Conditional Value at Risk (CVaR). We present an novel optimism-based algorithm for this setting: instead of adding bonuses to the CVaR estimate of each arm, we apply optimism at the sample level, generating an optimistic set of samples for each arm and then computing CVaR estimates from them instead. We present regret bounds for our algorithm, along with experiments showing order-of-magnitude improvements over baselines and prior work. Further experiments demonstrate how sample-level optimism enables our algorithm to adapt to the shape of each arm distribution in ways that exploration bonuses do not.

Summary¶

Constructs optimistic sample distributions using Dvoretzky-Kiefer-Wolfowitz confidence bands before estimating each arm's CVaR. Provides regret guarantees and experiments showing that distribution-aware exploration improves on bonuses applied directly to scalar CVaR estimates.

Links¶

Tags¶

Similar Papers¶