Contextual multi-armed bandit (MAB) algorithms have been shown promising for maximizing cumulative rewards in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. However, most of the proposed contextual MAB algorithms assume linear relationships be…
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “contextual MAB”
In this work, we study recommendation systems modelled as contextual multi-armed bandit (MAB) problems. We propose a graph-based recommendation system that learns and exploits the geometry of the user space to create meaningful clusters in the user domain. This reduces the dimensionality of the recommendation problem w…
There are two variants of the classical multi-armed bandit (MAB) problem that have received considerable attention from machine learning researchers in recent years: contextual bandits and simple regret minimization. Contextual bandits are a sub-class of MABs where, at every time step, the learner has access to side in…
New algorithm for contextual combinatorial bandits with probabilistic arm triggering.
problem Optimizing decisions in dynamic environments with probabilistic arm availability.
method C^2-UCB-T and VAC^2-UCB algorithms with TPM and VM conditions.
result Achieved improved regret bounds for contextual combinatorial bandits.
We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed…
Two new algorithms improve online clustering of bandits by accelerating cluster identification without strong assumptions.
problem Challenges in accurately identifying unknown user clusters in online bandit settings.
method Proposes UniCLUB and PhaseUniCLUB algorithms with enhanced exploration mechanisms.
result Achieves comparable regret bounds to prior work with weaker assumptions.
The (contextual) multi-armed bandit problem (MAB) provides a formalization of sequential decision-making which has many applications. However, validly evaluating MAB policies is challenging; we either resort to simulations which inherently include debatable assumptions, or we resort to expensive field trials. Recently …
Novel algorithm reduces feature inclusion in online decision-making.
problem Optimizing decision-making for personalized user experiences with fairness.
method Online Batched Sequential Inclusion (OBSI) algorithm for sequential feature inclusion.
result OBSI outperforms other algorithms in terms of regret, relevance of features, and compute.
Develops locally private methods for nonparametric contextual bandits.
problem Privacy concerns in sequential decision-making on sensitive data.
method Uniform-confidence-bound-type estimator and jump-start scheme.
result Minimax optimality of proposed methods supported by lower bounds.
In recent years, multi-armed bandit (MAB) framework has attracted a lot of attention in various applications, from recommender systems and information retrieval to healthcare and finance, due to its stellar performance combined with certain attractive properties, such as learning from less feedback. The multi-armed ban…
The problem of multi-armed bandits (MAB) asks to make sequential decisions while balancing between exploitation and exploration, and have been successfully applied to a wide range of practical scenarios. Various algorithms have been designed to achieve a high reward in a long term. However, its short-term performance m…
Proposes a max-utility arm selection strategy for reducing cumulative regret in sequential query recommendations.
problem Reduces cumulative regret in sequential query recommendations for closed loop interactive learning settings.
method Proposes a max-utility arm selection strategy based on the maximum utility of arms.
result Improves cumulative regret substantially compared to baseline algorithms and random selection.
Paper introduces a new analysis framework for stochastic linear bandits.
problem Optimizing decision-making in online experiments with noisy rewards.
method Develops a general analysis framework and algorithms for stochastic linear bandits.
result Introduces new algorithms like SG that improve performance and provide new regret bounds.
Unified framework for human-like decision making in various sequential tasks.
problem Real-life decision-making involves diverse strategies leading to similar outcomes.
method Two-stream reward processing mechanism for flexible and unified models.
result Framework unified MAB, CB, and RL with comparable performance.
New algorithm for traffic routing in congested conditions.
problem Optimal routing in congested traffic networks.
method Congested Bandits model, UCB algorithm, iterative least squares planner.
result No-regret algorithms for congestion-aware routing.
HATCH learns optimal recommendations with resource constraints.
problem Resource-constrained recommendation systems.
method Hierarchical adaptive contextual bandits with adaptive resource allocation.
result HATCH achieves a regret bound of .
New method tracks significant shifts in nonparametric bandits.
problem Tracking significant changes in nonparametric contextual bandits.
method Proposed a notion of 'experienced significant shifts' to adapt to minimax rate without knowledge of change parameters.
result Experienced significant shifts count fewer changes than traditional metrics, leading to an adaptive algorithm.
Paper closes the gap in MP-MAB problems with novel adaptive communication and exploration.
problem Closing the gap between decentralized MP-MAB and natural centralized lower bound.
method BEACON: Batched Exploration with Adaptive COmmunicatioN, incorporating ADC and batched exploration.
result Proves logarithmic regret for a generalized MP-MAB problem.
We formulate the problem of sampling and recovering clustered graph signal as a multi-armed bandit (MAB) problem. This formulation lends naturally to learning sampling strategies using the well-known gradient MAB algorithm. In particular, the sampling strategy is represented as a probability distribution over the indiv…
A new bandit problem where experiments can be interrupted if results are not promising.
problem Interruptible multi-armed bandit problem with a threshold for cumulative reward.
method Formalized survival regret, identified key components (regret and probability of ruin), derived lower bounds and optimal policies.
result No policy can achieve sublinear survival regret, but optimal policies minimize survival regret in a Pareto sense.
We extend Bayesian multi-armed bandit (MAB) algorithms beyond their original setting by making use of sequential Monte Carlo (SMC) methods. A MAB is a sequential decision making problem where the goal is to learn a policy that maximizes long term payoff, where only the reward of the executed action is observed. In the …
New algorithms detect changes in non-stationary MABs for better performance.
problem Non-stationary MAB environments where arm reward distributions change over time.
method Modular Detection Augmented Bandit (DAB) procedures with improved performance lower bounds.
result Modular DAB procedures achieve order-optimal regret bounds for various change detectors and bandit algorithms.
Trust-aware MAB improves learning performance by accounting for human deviation.
problem Learning performance suffers when humans deviate from recommended policies due to lack of trust.
method Integrates a dynamic trust model into MAB framework, establishing minimax regret and proposing a two-stage trust-aware procedure.
result Proves near-optimal statistical guarantees for trust-aware MAB algorithms.
LNUCB-TA improves MAB performance by dynamically adjusting exploration rates and recognizing spatiotemporal patterns.
problem Suboptimal performance in environments with rapidly changing reward structures and static exploration rates.
method Hybrid model combining linear and nonlinear estimation, with adaptive k-NN for temporal attention.
result Significantly outperforms state-of-the-art algorithms in cumulative and mean reward, convergence, and robustness.
Multi-Armed Bandit Strategies for Non-Stationary Reward Distributions and Delayed Feedback Processescs.LG
A survey is performed of various Multi-Armed Bandit (MAB) strategies in order to examine their performance in circumstances exhibiting non-stationary stochastic reward functions in conjunction with delayed feedback. We run several MAB simulations to simulate an online eCommerce platform for grocery pick up, optimizing …
This review examines bandit problems in AI using statistical methods.
problem Sequential decision-making under uncertainty in AI environments.
method Foundational models, concentration inequalities, minimax regret bounds, frequentist and Bayesian algorithms, K-armed contextual bandits, SCAB, functional data analysis.
result Exploration-exploitation trade-offs and regret analyses in various bandit problems.
New algorithm for multi-fidelity bandits reduces costs and improves regret.
problem Optimizing decisions with varying costs and accuracy in multi-fidelity bandits.
method Cost complexity bounds, algorithmic framework, elimination-based algorithm.
result New regret definition and matching upper and lower bounds for elimination-based algorithm.
New algorithm ensures consistent results in constrained MAB problems.
problem Achieving consistent results in constrained MAB problems.
method Developed replicable algorithms for constrained MAB problems using the optimism principle.
result Regret and constraint violation of replicable algorithms match those of non-replicable ones.
INF-clip optimizes heavy-tailed MAB problems with improved performance.
problem Optimizing multi-armed bandit problems with heavy-tailed rewards.
method INF-clip algorithm for adversarial and stochastic heavy-tailed MAB settings.
result INF-clip is optimal for linear and non-linear heavy-tailed stochastic MAB problems.
In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension of the classical stochastic MAB model. In the BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regr…
Rotting Banditsstat.ML
The Multi-Armed Bandits (MAB) framework highlights the tension between acquiring new knowledge (Exploration) and leveraging available knowledge (Exploitation). In the classical MAB problem, a decision maker must choose an arm at each time step, upon which she receives a reward. The decision maker's objective is to maxi…
Instrument-Armed Banditsstat.ML
We extend the classic multi-armed bandit (MAB) model to the setting of noncompliance, where the arm pull is a mere instrument and the treatment applied may differ from it, which gives rise to the instrument-armed bandit (IAB) problem. The IAB setting is relevant whenever the experimental units are human since free will…
New MAB model for online caching costs.
problem Learning costs of cached items online.
method Synchronization bandits, MirrorSync algorithm.
result Adversarial regret of for MirrorSync.
Chronological Causal Banditsstat.ML
Chronological Causal Bandits (CCB) tackles dynamic causal decision-making.
problem Dynamic causal decision-making in a system where rewards depend on past interventions.
method Introduces a new MAB problem (Chronological Causal Bandit) where rewards are influenced by a dynamic causal model.
result Early findings show the CCB can transfer information between sequential MABs.
Develops Thompson Sampling algorithms for mean-variance bandits.
problem Risk in online decision making systems.
method Thompson Sampling algorithms for mean-variance MAB with comprehensive regret analyses.
result Achieves best known regret bounds for mean-variance MABs and information-theoretic bounds in some regimes.
New TS algorithms improve performance in non-stationary multi-armed bandit problems.
problem Sequential decision-making with evolving action rewards.
method Sliding-window Thompson sampling approaches with different priors.
result Unified regret upper bound for arbitrary non-stationary MABs.
We propose an alternative framework to existing setups for controlling false alarms when multiple A/B tests are run over time. This setup arises in many practical applications, e.g. when pharmaceutical companies test new treatment options against control pills for different diseases, or when internet companies test the…
This paper deals with bandit online learning problems involving feedback of unknown delay that can emerge in multi-armed bandit (MAB) and bandit convex optimization (BCO) settings. MAB and BCO require only values of the objective function involved that become available through feedback, and are used to estimate the gra…
New MAB model incentivizes user arm-pulling with self-reinforcing preferences.
problem Balancing exploration and exploitation in recommender systems with incentivized user preferences.
method Proposes a new MAB model with random arm selection and two policies: At-Least- Explore-Then-Commit and UCB-List.
result Achieves expected regret and expected payment over a time horizon .
New L2 regularization improves softmax MAB performance.
problem Improving softmax MAB performance with vanishing regularization.
method L2 regularization with vanishing parameter analyzed and proven convergent.
result Vanishing L2 regularization makes softmax MAB more numerically advantageous.
A scheme robust to action erasures improves MAB performance.
problem Learning in multi-arm bandits with erasure channels.
method Proposes a scheme to work on top of any MAB algorithm.
result Worst-case regret is at most a factor of away from no-erasure case.
This paper analyzes the multi-armed bandit model using path-integral methods.
problem Understanding the stochastic dynamics and optimal strategies in multi-armed bandit problems.
method Path-integral analysis of statistical physics.
result Emergence of multimodal regret distribution with large regrets from exploitation of sub-optimal arms.
Paper proposes CVaR-TS for risk-constrained MAB problems.
problem Risk in decision-making complicates reward maximization in MAB problems.
method Risk measure CVaR is used, and Thompson Sampling is adapted for CVaR.
result CVaR-TS outperforms other L/UCB-based algorithms in risk-constrained MAB settings.
We study a policy gradient method with L2 regularization for MAB problems.
problem Improving policy gradient methods for MAB problems with regularization.
method Investigate convergence of a policy gradient algorithm with L2 regularization for MAB.
result Prove convergence under appropriate technical hypotheses and show practical improvements.
The paper studies MAB problems with LDP to balance privacy and service quality.
problem Balancing privacy and service quality in multi-armed bandit systems.
method Investigates regret minimization for MAB with LDP guarantee, proving lower bounds and proposing matching upper bounds algorithms.
result Regret upper bounds match lower bounds up to constant factors for MAB algorithms with LDP guarantee.
This paper proposes a general framework of multi-armed bandit (MAB) processes by introducing a type of restrictions on the switches among arms evolving in continuous time. The Gittins index process is constructed for any single arm subject to the restrictions on switches and then the optimality of the corresponding Git…
New algorithm identifies optimal actions in large reward spaces efficiently.
problem Finding the best action from a large set of options with minimal trials.
method GenTS-Explore algorithm for real-valued combinatorial pure exploration.
result Achieves optimal sample complexity for large action sets.
In a multi-armed bandit (MAB) problem a gambler needs to choose at each round of play one of K arms, each characterized by an unknown reward distribution. Reward realizations are only observed when an arm is selected, and the gambler's objective is to maximize his cumulative expected earnings over some given horizon of…