Paper introduces Decentralized Non-stationary Competing Bandits ( exttt{DNCB}) for dynamic matching markets.
problem Understanding dynamic two-sided matching markets with competing agents.
method Proposes a decentralized asynchronous learning algorithm ( exttt{DNCB}) for non-stationary environments.
result Obtains sub-linear (logarithmic) regret of exttt{DNCB} in dynamic settings.
A blockchain protocol uses bandit algorithms to dynamically price transactions.
problem Maximizing revenue from decentralized blockchain Indexers competing for queries.
method Dynamic pricing using Gaussian bandits for multiple agents.
result Improved revenue through dynamic pricing in a decentralized blockchain environment.
Decentralized learning for matching markets with time-varying preferences.
problem Matching between competing agents and supply arms with time-varying preferences.
method Linear contextual bandit framework, learning algorithms to identify latent environment and stable matchings.
result Achieve instance-dependent logarithmic regret, applicable for large markets.
New algorithm optimizes unimodal bandits using empirical divergence.
problem Optimizing decisions in multi-armed bandit problems with unimodal distributions.
method Indexed Minimum Empirical Divergence (IMED) adapted for unimodal structure.
result IMED-UB algorithm optimally exploits unimodal structure.
A new algorithm for competing agents in a two-sided market setting.
problem Decentralized competition between agents in a two-sided market with unknown valuations.
method UCB-D3 algorithm for UCB with Decentralized Dominant-arm Deletion.
result UCB-D3 is order optimal and achieves a new regret lower bound.
Improves online learning with expert demonstrations, quality matters.
problem Improving online learning through offline demonstration data.
method Thompson sampling applied to a multi-armed bandit model, informed by expert demonstrations and Bayes' rule.
result Substantial empirical regret reduction with expert demonstrations, improving online performance.
We study contextual bandit learning with an abstract policy class and continuous action space. We obtain two qualitatively different regret bounds: one competes with a smoothed version of the policy class under no continuity assumptions, while the other requires standard Lipschitz assumptions. Both bounds exhibit data-…
Proposes a Thompson sampling algorithm for multi-objective contextual bandit problems with auxiliary constraints.
problem Real-world applications with multiple competing objectives and auxiliary constraints.
method Thompson sampling algorithm for multi-outcome contextual bandit problems with auxiliary constraints.
result Empirically evaluated and applied to a real-world video transcoding problem.
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 pc per round. The agents and player choose one of three options: (1) Exploit (a …
Algorithm provides online learning guarantees against general comparators in full and bandit feedback.
problem Adversarial online learning with data-dependent regret guarantees.
method Completely online algorithm with data-dependent regret guarantees for full and bandit feedback.
result Algorithm achieves expected performance against arbitrary comparator sequences in full and bandit feedback settings.
Algorithm reduces regret in non-stationary bandits and meta-learning with optimal arms.
problem Sequential decision-making with changing task boundaries and optimal arms.
method Reduction to bandit submodular maximization, meta-learning algorithms.
result Regret bounds for both non-stationary and bandit meta-learning problems.
GPE algorithm optimizes nonparametric contextual bandits with efficient regret bounds.
problem Optimizing nonparametric contextual bandits with efficient regret bounds.
method Inspired by Policy Elimination, GPE uses oracle-efficient techniques for nonparametric classes with infinite VC-dimension.
result GPE is regret-optimal for policy classes with integrable entropy, and for larger entropy, it provides an ε-greedy algorithm with matching regret bounds. Stable matching, a classical model for two-sided markets, has long been studied with little consideration for how each side's preferences are learned. With the advent of massive online markets powered by data-driven matching platforms, it has become necessary to better understand the interplay between learning and mark…
We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of K actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problem…
New algorithm handles bandit problems under translations and scales.
problem Adversarial multi-armed bandit problems with arbitrary translations and scales.
method Innovative online algorithm invariant to translations and scales, using universal prediction.
result Second-order regret bounds, unaffected by affine transformations of losses.
New algorithm reduces regret for many bandit algorithms with logarithmic dependence on number of algorithms.
problem Combining and learning over a large set of adversarial bandit algorithms to track the best one.
method Proposes a new algorithm (CORRAL) with logarithmic regret dependence on the number of base algorithms.
result Achieves optimal switching regret for adversarial linear bandits over a d-dimensional ℓp unit-ball. Study explores strategies for randomized allocation in delayed rewards bandits.
problem Understanding the exploration-exploitation tradeoff in randomized strategies with delayed rewards.
method Examines two strategies: updating exploration sequence at every time point vs. updating only when a new reward is observed.
result The strategy updating only when a new reward is observed leads to strong consistency in allocation for a wider scope of situations.
New algorithm reduces best-in-class regret in contextual bandits.
problem Compete with the best policy in a class without model restrictions.
method Proposes an algorithm that updates policies by minimizing a pessimistic objective, including a clipped inverse-propensity estimate and variance penalty.
result Achieves fast best-in-class regret rates, including polylogarithmic rates in the parametric case.
We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity const…
New algorithm for competing influence spread in unknown networks.
problem Maximizing influence spread in a social network with unknown probabilities.
method Combinatorial multi-armed bandit (CMAB) framework, Triggering Probability Modulated (TPM) condition, OCIM-TS, OCIM-OFU, OCIM-ETC.
result Sublinear Bayesian and frequentist regret for OCIM-TS and OCIM-OFU, respectively.
Unified framework controls false discovery rate in bandit multiple testing.
problem Designing adaptive algorithms to identify true discoveries in multiple hypothesis testing.
method Unified modular framework using e-processes for FDR control in arbitrary settings.
result Unified framework ensures FDR control for dependent and simultaneous arm queries.
New metric measures variability in bandit algorithms, linking regret and variability.
problem Variability in multi-armed bandit allocations harms modern applications.
method Introduces allocation variability as a new metric and establishes a trade-off with regret.
result Any minimax regret-optimal algorithm must incur worst-case allocation variability Θ(T).
Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. …
New algorithms improve exploration in unbounded reward settings.
problem Challenges in exploration with unbounded rewards in reinforcement learning.
method Proposed EXP4.P and EXP4-RL algorithms for unbounded reward settings.
result EXP4.P achieves global optimality in linear cases with one competent expert.
Study uses contextual bandits to optimize charity exposure in donation solicitation.
problem Optimizing charity exposure in donation solicitation using survey responses.
method Adaptive experiment design to balance cumulative regret minimization and simple regret minimization.
result Adaptive experimentation yields better policy learning outcomes than uniform randomization.
New method reduces bias in learning from large action spaces using selective importance sampling.
problem Learning from large-scale recommendation systems with bandit feedback and supervised labels.
method Selective Importance Sampling (sIS) and Policy Optimization for eXtreme Models (POXM) algorithm.
result POXM method significantly outperforms existing methods in learning from bandit feedback on XMC tasks.
In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the hig…
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 …
New algorithm for identifying optimal arms in stochastic bandit problems.
problem Optimal arm identification in stochastic bandit problems with many arms.
method Characterized optimal learning rates and provided algorithms with matching bounds.
result Lower bounds and matching upper bounds for cumulative regret and best-arm identification.
Efficient algorithm for mobile health provides timely physical activity suggestions.
problem Inefficient reinforcement learning for mobile health settings.
method Contextual bandit algorithm with linear mixed effects model and hyper-parameter updating.
result Improves speed and accuracy by up to 99% and 56%.
We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be bel…
The stochastic multi-armed bandit (MAB) problem is a common model for sequential decision problems. In the standard setup, a decision maker has to choose at every instant between several competing arms, each of them provides a scalar random variable, referred to as a "reward." Nearly all research on this topic consider…
New algorithm minimizes regret in multi-armed bandits with network interference.
problem Minimizing regret in online experiments with network interference.
method Sparse network interference model, discrete Fourier analysis, linear regression-based algorithms.
result Provable low regret algorithms for sparse interference networks.
We study the problem of repeated play in a zero-sum game in which the payoff matrix may change, in a possibly adversarial fashion, on each round; we call these Online Matrix Games. Finding the Nash Equilibrium (NE) of a two player zero-sum game is core to many problems in statistics, optimization, and economics, and fo…
Mathematical approach assesses human resource competences accurately.
problem Accurate assessment and representation of human resource competences.
method Detailed quantification scheme and mathematical approach.
result Flexible tools for optimal job assignment and recruitment.
Paper improves competence estimation of machine learning models.
problem Estimating machine learning performance in real-world scenarios.
method ALICE Score: a pointwise competence estimator considering distributional, data, and model uncertainty.
result Significant improvements in competence prediction over state-of-the-art methods.
Dynamic Ensemble Selection (DES) techniques aim to select locally competent classifiers for the classification of each new test sample. Most DES techniques estimate the competence of classifiers using a given criterion over the region of competence of the test sample (its the nearest neighbors in the validation set). T…
New pricing algorithm learns demand curves and optimizes prices in dynamic markets.
problem Dynamic pricing in markets with incomplete demand information and shifting conditions.
method Actor-Critic Information-Directed Pricing (ACIDP) using IDS algorithms and auditing procedures.
result ACIDP outperforms UCB and TS in market environment shifts.
Dynamic regressor selection (DRS) systems work by selecting the most competent regressors from an ensemble to estimate the target value of a given test pattern. This competence is usually quantified using the performance of the regressors in local regions of the feature space around the test pattern. However, choosing …
Algorithm solves two-sided matching markets with unknown preferences and constraints.
problem Two-sided online matching markets with complementary preferences and quota constraints.
method Formulated as a bandit learning problem, proposed MMTS algorithm combining Thompson Sampling and double matching.
result MMTS achieves stability and linear Bayesian regret with respect to quota and time horizon.
Maximising the detection of intrusions is a fundamental and often critical aim of perimeter surveillance. Commonly, this requires a decision-maker to optimally allocate multiple searchers to segments of the perimeter. We consider a scenario where the decision-maker may sequentially update the searchers' allocation, lea…
Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive …
Comprisk simplifies competing-risks analysis in Python.
problem Analyzing medical time-to-event data with competing risks.
method A scikit-learn-compatible toolkit for competing-risks survival analysis.
result Comprisk provides a unified API for various competing-risks methods.
Real-time bidding (RTB) systems, which utilize auctions to allocate user impressions to competing advertisers, continue to enjoy success in digital advertising. Assessing the effectiveness of such advertising remains a challenge in research and practice. This paper proposes a new approach to perform causal inference on…
SurvivalBoost improves prediction of event times in competing risks scenarios.
problem Predicting event times in scenarios with multiple possible outcomes.
method Developed a strictly proper censoring-adjusted scoring rule for stochastic optimization of competing risks.
result SurvivalBoost outperforms 12 state-of-the-art models across various metrics.
Survival analysis in the presence of multiple possible adverse events, i.e., competing risks, is a pervasive problem in many industries (healthcare, finance, etc.). Since only one event is typically observed, the incidence of an event of interest is often obscured by other related competing events. This nonidentifiabil…
Competency questions help experts select best clustering for energy data.
problem Ad hoc and subjective selection of clustering structures by domain experts.
method Formalize expert knowledge and requirements with competency questions.
result Competency questions improve reproducibility and evaluation of clustering applications.
This paper uses neural networks to accurately model competing risks in survival analysis.
problem Ignoring competing risks leads to biased survival estimation in machine learning models.
method The paper introduces constrained monotonic neural networks to model each competing survival distribution.
result The method ensures exact likelihood maximization with reduced computational cost.