A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Paper tackles good arm identification in stochastic bandits.
New algorithms find all ε-good arms in stochastic bandits.
New algorithm identifies good arms with fewer samples when thresholds are close.
APGAI identifies good arms anytime with fixed budget.
We consider a novel stochastic multi-armed bandit problem called {\em good arm identification} (GAI), where a good arm is defined as an arm with expected reward greater than or equal to a given threshold. GAI is a pure-exploration problem that a single agent repeats a process of outputting an arm as soon as it is ident…
This work optimizes identifying good arms in nonparametric multi-armed bandits.
New method for identifying best arm in batched multi-armed bandit problems.
Simple greedy algorithms can excel in multi-objective bandits with multiple good arms.
We study the problem of identifying the top arms in a multi-armed bandit game. Our proposed solution relies on a new algorithm based on successive rejects of the seemingly bad arms, and successive accepts of the good ones. This algorithmic contribution allows to tackle other multiple identifications settings that w…
We consider the problem of minimizing the regret in stochastic multi-armed bandit, when the measure of goodness of an arm is not the mean return, but some general function of the mean and the variance.We characterize the conditions under which learning is possible and present examples for which no natural algorithm can…
Improved theoretical guarantees for Top Two algorithms.
We consider the problem of identifying any out of the best arms in an -armed stochastic multi-armed bandit. Framed in the PAC setting, this particular problem generalises both the problem of `best subset selection' and that of selecting `one out of the best m' arms [arcsk 2017]. In applications such as crowd…
We present a formal model of human decision-making in explore-exploit tasks using the context of multi-armed bandit problems, where the decision-maker must choose among multiple options with uncertain rewards. We address the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and …
This paper considers a multi-armed bandit game where the number of arms is much larger than the maximum budget and is effectively infinite. We characterize necessary and sufficient conditions on the total budget for an algorithm to return an ε-good arm with probability at least 1 - δ. In such situations, the sample com…
New algorithm improves online decision making by adaptively inferring arm rewards.
Improved knowledge gradient (iKG) outperforms the original KG algorithm in best arm identification problems.
New algorithm for identifying optimal arms in stochastic bandit problems.
We consider two multi-armed bandit problems with arms: (i) given an , identify an arm with mean that is within of the largest mean and (ii) given a threshold and integer , identify arms with means larger than . Existing lower bounds and algorithms for the PAC framework suggest that both …
We consider the stochastic multi-armed bandit problem and the contextual bandit problem with historical observations and pre-clustered arms. The historical observations can contain any number of instances for each arm, and the pre-clustering information is a fixed clustering of arms provided as part of the input. We de…
Proper balance between exploitation and exploration is what makes good decisions, which achieve high rewards like payoff or evolutionary fitness. The Infomax principle postulates that maximization of information directs the function of diverse systems, from living systems to artificial neural networks. While specific a…
New algorithm minimizes regret in multi-armed bandits with network interference.
New algorithm identifies optimal subtrees in fixed-budget tree search.
New algorithm models satiation in recommender systems.
New algorithms solve complex function optimization problems.
Paper proposes Adaptive Pareto Exploration for identifying Pareto optimal arms in multi-objective scenarios.
We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability per round. The agents and player choose one of three options: (1) Exploit (a …
The paper emphasizes the importance of joint predictions over marginal predictions for decision-making.
We describe a novel algorithm for noisy global optimisation and continuum-armed bandits, with good convergence properties over any continuous reward function having finitely many polynomial maxima. Over such functions, our algorithm achieves square-root regret in bandits, and inverse-square-root error in optimisation, …
We study the problem of using causal models to improve the rate at which good interventions can be learned online in a stochastic environment. Our formalism combines multi-arm bandits and causal inference to model a novel type of bandit feedback that is not exploited by existing approaches. We propose a new algorithm t…
We consider the decentralized exploration problem: a set of players collaborate to identify the best arm by asynchronously interacting with the same stochastic environment. The objective is to insure privacy in the best arm identification problem between asynchronous, collaborative, and thrifty players. In the context …
Incentive-aware recommender system for online platforms.
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 …
DART optimizes subset selection in non-linear bandit problems.
TRIPLE efficiently optimizes prompts with a budget constraint.
This paper analyzes the multi-armed bandit model using path-integral methods.
New algorithm reduces sample complexity for Top Two method.
Active learning aims to reduce annotation cost by predicting which samples are useful for a human teacher to label. However it has become clear there is no best active learning algorithm. Inspired by various philosophies about what constitutes a good criteria, different algorithms perform well on different datasets. Th…
Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multi-armed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms f…
New bandit model for healthcare intervention planning.
Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, . In many applications ho…
The pair-matching problem appears in many applications where one wants to discover good matches between pairs of entities or individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and obs…
New study on regret lower bounds for multi-agent multi-armed bandit problems.
New algorithms identify Pareto optimal sets in multi-objective bandit problems.
Unified algorithm for efficient pure exploration using dual variables.
Pure exploration (aka active testing) is the fundamental task of sequentially gathering information to answer a query about a stochastic environment. Good algorithms make few mistakes and take few samples. Lower bounds (for multi-armed bandit models with arms in an exponential family) reveal that the sample complexity …
The paper addresses privacy-preserving BAI in clinical trials and user studies.
The paper studies privacy-protected BAI with fixed confidence, deriving lower bounds and proposing an adaptive algorithm.
Multi-user multi-armed bandits have emerged as a good model for uncoordinated spectrum access problems. In this paper we consider the scenario where users cannot communicate with each other. In addition, the environment may appear differently to different users, , the mean rewards as observed by different users…