arXiv research

Paper confirms Feldman's conjecture on two-armed bandit problem.

This paper refines the weighted strategy for non-stationary parametric bandits, improving regret bounds.

This paper refines the weighted strategy for non-stationary parametric bandits and MDPs, improving regret bounds.

New strategies avoid forced exploration for unimodal bandits.

New algorithm tackles adversarial bandits with arbitrary strategies.

Study explores strategies for randomized allocation in delayed rewards bandits.

Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world appli…

Balances the regret of different algorithms in bandit and RL problems.

The paper explores MAB strategies for very short horizons, introducing new methods and showing improved performance.

Improved elimination strategies for adaptive bandit identification reduce sample complexity and computational burden.

Optimal strategy found for identifying best arm in bandits with small gap.

BIS uses bandits to efficiently sample from expensive-to-evaluate densities.

New strategy achieves optimal regret without communication or collisions in multi-player bandit.

A new exploration strategy for contextual bandits reduces regret and is computationally efficient.

We consider a scenario where an agent has multiple available strategies to explore an unknown environment. For each new interaction with the environment, the agent must select which exploration strategy to use. We provide a new strategy-agnostic method that treat the situation as a Multi-Armed Bandits problem where the…

New strategy optimally identifies best arm in unknown variance Gaussian bandits.

We propose a contextual-bandit approach for demand side management by offering price incentives. More precisely, a target mean consumption is set at each round and the mean consumption is modeled as a complex function of the distribution of prices sent and of some contextual variables such as the temperature, weather, …

Proposes EE-Net for neural exploration in contextual bandits.

Meta-learning improves performance in stochastic linear bandits.

A new strategy for identifying the best arm in Gaussian bandits with improved exploration.

As the cornerstone of modern portfolio theory, Markowitz's mean-variance optimization is considered a major model adopted in portfolio management. However, due to the difficulty of estimating its parameters, it cannot be applied to all periods. In some cases, naive strategies such as Equally-weighted and Value-weighted…

A new bandit strategy improves learning speed at the cost of accuracy.

We describe MELEE, a meta-learning algorithm for learning a good exploration policy in the interactive contextual bandit setting. Here, an algorithm must take actions based on contexts, and learn based only on a reward signal from the action taken, thereby generating an exploration/exploitation trade-off. MELEE address…

Algorithm reduces regret in multi-player bandits with unknown collision rewards.

The paper extends physics-based information maximization to complex bandit problems.

New strategy identifies best Markovian arm with fixed confidence.

Polynomial-time method solves complex combinatorial semi-bandits.

New algorithms boost SAT solver performance by optimizing restart strategies.

New algorithm tackles delayed feedback in Lipschitz bandits with sublinear regret.

Presents SPEED, an algorithm for optimal policy evaluation in linear bandits with heteroscedastic noise.

New strategies improve multi-agent decision-making on irregular networks.

Study examines impact of missing data on multi-armed bandit algorithms.

We propose $\tt RandUCB$, a bandit strategy that builds on theoretically derived confidence intervals similar to upper confidence bound (UCB) algorithms, but akin to Thompson sampling (TS), it uses randomization to trade off exploration and exploitation. In the $K$-armed bandit setting, we show that there are infinitel…

A meta-UCB method combines stochastic bandit algorithms.

Aims to optimize influence spread in social networks using bandit algorithms.

We introduce a novel algorithmic approach to content recommendation based on adaptive clustering of exploration-exploitation ("bandit") strategies. We provide a sharp regret analysis of this algorithm in a standard stochastic noise setting, demonstrate its scalability properties, and prove its effectiveness on a number…

Optimal strategy proposed for maximizing cumulative reward in continuum-armed bandits.

Meta-learning bandits by reducing dimensionality with PCA.

Multi-armed bandit problems are receiving a great deal of attention because they adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a…

The paper tackles pure exploration in multi-armed bandits with low rank structure using oblivious sampling.

For the stochastic multi-armed bandit (MAB) problem from a constrained model that generalizes the classical one, we show that an asymptotic optimality is achievable by a simple strategy extended from the $ε_t$-greedy strategy. We provide a finite-time lower bound on the probability of correct selection of an optimal ne…

Regularization-induced exploration improves contextual bandit performance.

We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from $(\ln t)^3$ to $(\ln t)^2$ and eliminates an additive factor of o…

Study analyzes symmetric two-armed Bernoulli bandit problem with zero mean gap.

I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds…

In a linear stochastic bandit model, each arm is a vector in an Euclidean space and the observed return at each time step is an unknown linear function of the chosen arm at that time step. In this paper, we investigate the problem of learning the best arm in a linear stochastic bandit model, where each arm's expected r…

HAMLET optimizes algorithm selection for machine learning tasks.

We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity $H$, will misidentify the best arm with pr…