New algorithm improves learning efficiency in multi-task contextual bandits.
problem Improving learning efficiency in multi-task contextual bandits.
method Alternating projected gradient descent (GD) and minimization estimator for low-rank feature matrix recovery.
result Proved regret bound for multi-task learning algorithm.
PAC-Bayesian analysis improves lifelong learning in multi-armed bandits.
problem Improving lifelong learning in multi-armed bandits.
method PAC-Bayesian analysis for deriving lower bounds and proposing lifelong learning algorithms.
result Proposed algorithms outperform baseline methods in lifelong multi-armed bandit problems.
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.
New algorithms minimize regret in multi-task and lifelong linear bandits with shared representation.
problem Minimizing regret in multi-task and lifelong linear bandits with shared representation.
method Novel algorithms using efficient estimator for low-rank linear feature extractor and novel analysis.
result Achieved regret bounds matching minimax lower bound up to logarithmic factors.
Meta-learning improves performance in stochastic linear bandits.
problem Selecting a learning algorithm that performs well across multiple bandit tasks.
method Regularized OFUL algorithm with a bias vector, estimating bias within the learning-to-learn setting.
result Meta-learning strategies improve performance when the number of tasks grows and task variance is small.
LIBO optimizes repeated bandit tasks without prior knowledge or regret.
problem Optimizing repeated bandit tasks without prior knowledge or regret.
method LIBO sequentially meta-learns a kernel to adapt to the environment and solve tasks with the latest estimate.
result LIBO achieves sublinear lifelong regret, converging to oracle performance as more tasks are solved.
New algorithms improve multi-task bandit performance by transferring reward samples.
problem Sequential multi-task bandit problems with adjacent similar tasks.
method Two UCB-based algorithms that transfer reward samples between tasks.
result Transfer of reward samples reduces overall regret compared to no transfer.
Unified meta-algorithm improves average performance across similar tasks in adversarial bandits.
problem Improving performance across multiple similar tasks in adversarial bandit settings.
method Unified meta-algorithm for multi-armed bandits and bandit linear optimization, tuning initialization, step-size, and entropy parameters.
result Unified meta-algorithm yields setting-specific guarantees for MAB and BLO, improving task-averaged regret.
The paper tackles lifelong learning in multi-armed bandits, aiming to minimize average regret over multiple tasks.
problem Minimizing average regret in multi-armed bandits over multiple tasks.
method Confidence interval tuning of UCB algorithms and greedy algorithms applied to a bandit over bandit approach.
result Empirical improvement over previous work in the mortal bandit problem.
Contextual bandits are a form of multi-armed bandit in which the agent has access to predictive side information (known as the context) for each arm at each time step, and have been used to model personalized news recommendation, ad placement, and other applications. In this work, we propose a multi-task learning frame…
Algorithm allocates budgets to tasks with semi-bandit feedback, achieving near-optimal regret bounds.
problem Stochastic budget allocation with censored semi-bandit feedback.
method Optimism-based algorithm operating under censored semi-bandit feedback.
result Regret scales polylogarithmically with horizon T in diminishing-returns regimes.
Study multi-task learning with low-rank representation in stochastic linear bandits.
problem Transfer learning across multiple linear bandit tasks with shared low-dimensional representation.
method Proposes a greedy policy with trace norm regularization to implicitly learn a low-rank representation without knowing the rank.
result Upper bound on multi-task regret of N d T ( T + d ) r \sqrt{NdT(T+d)r} N d T ( T + d ) r , showing benefit over independent task solving. Meta-learning for bandit tasks using shared representations.
problem Learning new bandit tasks efficiently using shared low-dimensional representations.
method Proposes a greedy policy to learn new bandit tasks leveraging a partially learned low-dimensional representation.
result Upper bound on regret of proposed policy, showing efficiency of learning new tasks.
Meta-learning bandits by reducing dimensionality with PCA.
problem Learning multiple bandit tasks with shared structure.
method Online Principal Component Analysis (PCA) for dimensionality reduction, combined with optimistic and Thompson sampling strategies.
result Significant reduction in expected regret compared to existing methods.
Transfer learning for bandits with latent Lipschitz continuity.
problem Learning to transfer structural information from prior tasks to new tasks.
method Proposes a framework to estimate Lipschitz constant from prior tasks and apply it to new tasks.
result Regret bound close to oracle algorithm with full knowledge of Lipschitz constant under mild assumptions.
Contextual multi-armed bandit problems arise frequently in important industrial applications. Existing solutions model the context either linearly, which enables uncertainty driven (principled) exploration, or non-linearly, by using epsilon-greedy exploration policies. Here we present a deep learning framework for cont…
Meta-learning improves performance across similar tasks in adversarial bandit settings.
problem Improving performance across multiple similar tasks in adversarial bandit scenarios.
method Designing meta-algorithms that combine outer learners to tune hyperparameters of inner learners for MAB and BLO.
result Meta-algorithms improve task-averaged regret for MAB and BLO, showing direct relationship with action space-dependent measures.
A TS algorithm improves performance in multi-task bandits with transfer.
problem Improving performance across multiple related bandit tasks.
method A TS-type algorithm for online multi-task learning with a novel concentration inequality.
result The TS-type algorithm achieves nearly-optimal performance guarantees.
Learning from prior tasks and transferring that experience to improve future performance is critical for building lifelong learning agents. Although results in supervised and reinforcement learning show that transfer may significantly improve the learning performance, most of the literature on transfer is focused on ba…
Optimal multitask learning method for sparse heterogeneous datasets.
problem Efficiently learning from multiple related datasets with sparse task-specific differences.
method MOLAR estimator, combining weighted median and shrinkage.
result Improves estimation error dependence on data dimension compared to task-wise least squares.
Novel approach to contextual bandits using self-supervised learning.
problem Exploiting rich data representations in computer vision without explicit labels.
method Combining contextual bandit objective with self-supervision objective.
result Substantial gains in cumulative reward on computer vision datasets.
New meta-learning framework for minimizing simple regret in bandits.
problem Minimizing simple regret in a sequence of bandit tasks with unknown distributions.
method Developed Bayesian and frequentist meta-learning algorithms for bandits, analyzing their meta simple regret.
result Bayesian algorithm achieves i l d e O ( m / n ) ilde{O}(m / \sqrt{n}) i l d e O ( m / n ) meta simple regret, frequentist algorithm i l d e O ( m n + m / n ) ilde{O}(\sqrt{m} n + m/ \sqrt{n}) i l d e O ( m n + m / n ) . New findings on complexity limits in fixed budget bandit identification.
problem Determining the best possible error rate for fixed budget bandit identification.
method Analyzing the best non-adaptive sampling procedures and showing the existence of complexities.
result No fixed complexity for certain bandit identification tasks.
Bandit structured prediction describes a stochastic optimization framework where learning is performed from partial feedback. This feedback is received in the form of a task loss evaluation to a predicted output structure, without having access to gold standard structures. We advance this framework by lifting linear ba…
Diffusion models help in learning priors for Thompson Sampling in bandit problems.
problem Learning effective strategies for diverse bandit tasks.
method Training a denoising diffusion model to learn task distributions, combining with Thompson Sampling.
result The approach significantly improves performance across different bandit tasks.
New algorithm reduces sample complexity for multi-task bandits.
problem Optimizing representation and predictor pairs for multi-task bandits.
method OSRL-SC algorithm with sample complexity H ( G log ( 1 / δ G ) + X log ( 1 / δ H ) ) H(G\log(1/δ_G)+ X\log(1/δ_H)) H ( G log ( 1/ δ G ) + X log ( 1/ δ H )) . result OSRL-SC algorithm approaches sample complexity lower bounds.
Stochastic Lipschitz bandit algorithms balance exploration and exploitation, and have been used for a variety of important task domains. In this paper, we present a framework for Lipschitz bandit methods that adaptively learns partitions of context- and arm-space. Due to this flexibility, the algorithm is able to effic…
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.
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…
The paper tackles carousel personalization in music streaming apps using contextual bandits.
problem Selecting relevant items to display in carousels for personalized content recommendation.
method Modeling carousel personalization as a contextual multi-armed bandit problem with multiple plays, cascade-based updates and delayed batch feedback.
result Empirically shows the effectiveness of the framework in capturing characteristics of real-world carousels.
Efficiently identifies best algorithms for game tasks.
problem Selecting optimal algorithms for game tasks efficiently.
method Best arm identification for multi-armed bandits with confidence intervals.
result Significantly improved performance in simple regret and error probability.
Algorithm aggregates rewards from multiple players to learn related tasks in online bandit learning.
problem Learning related but slightly different tasks in an online setting with heterogeneous feedback.
method RobustAgg ( ε ) (ε) ( ε ) algorithm that aggregates rewards from different players. result Achieves instance-dependent regret guarantees and nearly matching lower bounds.
NK bandits improve performance on nonlinear tasks.
problem Improving performance on nonlinear sequential decision tasks.
method Proposed NK bandits using neural kernels to guide policies.
result NK bandits achieve state-of-the-art performance.
BLOB combines organic and bandit signals for better user interest estimation.
problem Combining organic and bandit signals for improved user interest estimation.
method Bayesian Latent Organic Bandit (BLOB) model using variational auto-encoders and local re-parametrization.
result BLOB outperforms organic and bandit-based methods in both organic and bandit-rich environments.
Bayesian metalearning improves performance in linear bandits with misspecified priors.
problem Improper priors lead to suboptimal performance in sequential decision-making.
method Proves performance bounds for metalearning priors in stochastic linear bandits and develops a metalearning algorithm.
result Metalearning can improve performance by learning the prior from multiple tasks.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
Efficient boosting method for regression with limited feedback.
problem Online boosting for regression tasks with noisy multi-point bandit feedback.
method Efficient regret minimization method with online boosting algorithm and projection-free online convex optimization.
result Improved state-of-the-art guarantees in efficiency.
Study on the limits of bandit learning, showing hardness and limitations.
problem Understanding the learnability of bandit learning under arbitrary reward functions.
method Investigation into which classes of reward functions are learnable and how they can be learned.
result No combinatorial dimension can characterize bandit learnability, and computational hardness is inherent.
We analyze the K K K -armed bandit problem where the reward for each arm is a noisy realization based on an observed context under mild nonparametric assumptions. We attain tight results for top-arm identification and a sublinear regret of O ~ ( T 1 + D 2 + D ) \widetilde{O}\Big(T^{\frac{1+D}{2+D}}\Big) O ( T 2 + D 1 + D ) , where D D D is the context dimension, f…
Modified Meta-TS for linear contextual bandits reduces regret.
problem Optimizing decision-making in dynamic environments with context vectors.
method Meta-TSLB algorithm for linear contextual bandits, analyzing Bayes regret.
result Derives an O ( ( m + log ( m ) ) n log ( n ) ) O((m+\log(m))\sqrt{n\log(n)}) O (( m + log ( m )) n log ( n ) ) bound on Bayes regret. We present a study on reinforcement learning (RL) from human bandit feedback for sequence-to-sequence learning, exemplified by the task of bandit neural machine translation (NMT). We investigate the reliability of human bandit feedback, and analyze the influence of reliability on the learnability of a reward estimator,…
Stochastic structured prediction under bandit feedback follows a learning protocol where on each of a sequence of iterations, the learner receives an input, predicts an output structure, and receives partial feedback in form of a task loss evaluation of the predicted structure. We present applications of this learning …
Improved algorithms for stochastic linear bandits using tighter confidence sequences.
problem Stochastic linear bandits with improved worst-case regret guarantees.
method Novel tail bound for adaptive martingale mixtures to construct tighter confidence sequences.
result Linear bandit algorithm achieves competitive worst-case regret.
Algorithm identifies Copeland winners in dueling bandits with ternary feedback.
problem Identifying Copeland winners in dueling bandits with indifferences.
method Proposed POCOWISTA algorithm with a sample complexity close to lower bound.
result Algorithm shows excellent performance, even for conventional dueling bandits.
We introduce and describe the results of a novel shared task on bandit learning for machine translation. The task was organized jointly by Amazon and Heidelberg University for the first time at the Second Conference on Machine Translation (WMT 2017). The goal of the task is to encourage research on learning machine tra…
Paper tackles good arm identification in stochastic bandits.
problem Identifying good arms with minimal samples.
method Proposes DGAI, a differentiable algorithm to improve sample complexity.
result DGAI outperforms baseline algorithms in synthetic and real-world datasets.
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
Improves bandit convex optimization with gradient variations.
problem Bandit Convex Optimization with Gradient Variations.
method Refined analysis of non-consecutive gradient variation.
result Improved dimension dependence for convex and strongly convex functions.