Paper tackles noisy bandit feedback for multiclass classification.
problem Learning multiclass classifier with corrupted feedback.
method Proposes an unbiased estimator technique to estimate noise rates and an end-to-end framework.
result Algorithm achieves mistake bounds of O ( T ) O(\sqrt{T}) O ( T ) in high noise and O ( T i c e f r a c 23 ) O(T^{
icefrac{2}{3}}) O ( T i ce f r a c 2 3 ) in worst case. New algorithm optimizes functions in Matérn kernel RKHS with noisy feedback.
problem Optimizing functions in RKHS of Matérn kernel with noisy bandit feedback.
method π-GP-UCB algorithm with guaranteed sublinear regret for all ν > 1 and d ≥ 1.
result First practical approach with guaranteed sublinear regret for all ν > 1 and d ≥ 1.
New framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing ( α , β , δ , e x t t t N ) (α,β,δ, exttt{N}) ( α , β , δ , e x ttt N ) -resilience and developing a black-box framework. result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
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.
Algorithm learns fair division from noisy feedback in uncertain markets.
problem Learning fair division in uncertain markets with noisy feedback.
method Wrapper algorithms using dual averaging to learn item and agent values from bandit feedback.
result Asymptotically achieves optimal Nash social welfare in linear Fisher markets.
New algorithm optimizes noisy function evaluations with delayed feedback.
problem Optimizing unknown functions from noisy, delayed feedback.
method Kernel bandit problem with stochastically delayed feedback.
result Proposes an algorithm with improved regret bound for non-smooth kernels.
This paper tackles learning Stackelberg equilibrium in asymmetric games efficiently from noisy samples.
problem Learning Stackelberg equilibrium in asymmetric, general-sum games efficiently from noisy samples.
method The paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in bandit feedback setting.
result Sharp positive results on sample-efficient learning of Stackelberg equilibrium with value optimal up to a fundamental gap identified.
SCaLE tackles dynamic regret in noisy bandit feedback with switching costs.
problem Unbounded metric movement costs in bandit online convex optimization.
method SCaLE algorithm for high-dimensional dynamic quadratic hitting costs and ℓ 2 \ell_2 ℓ 2 -norm switching costs, with spectral regret analysis. result First algorithm achieving sub-linear dynamic regret without hitting cost knowledge.
Neural algorithms optimize arm selection with human preference feedback for complex reward functions.
problem Optimizing arm selection with noisy human preference feedback for complex, non-linear reward functions.
method Neural network to estimate reward function using preference feedback, upper confidence bound and Thompson sampling algorithms.
result Sub-linear regret guarantees for efficient arm selection in contextual dueling bandits.
A method identifies abrupt changes in functions with fixed confidence under noisy feedback.
problem Identifying abrupt changes in piecewise constant functions quickly and with certainty.
method Fixed-confidence piecewise constant bandit problem, focusing sampling efforts near change points.
result Asymptotically optimal method proven computationally efficient and effective in experiments.
New algorithms improve on bandit feedback in matrix games with unknown payoff matrices.
problem Improving performance in matrix games with unknown payoff matrices and bandit feedback.
method Regret analyses of variants of UCB and K-learning.
result New algorithms achieve lower regret compared to adversarial bandit algorithms.
New algorithms for optimizing functions with noisy feedback, even when the model is misspecified.
problem Optimizing a black-box function with noisy bandit feedback, especially when the model is misspecified.
method Developed two algorithms based on Gaussian process methods: EC-GP-UCB and Phased GP Uncertainty Sampling.
result Achieved optimal dependence on misspecification error without prior knowledge, and effective in stochastic contextual settings.
New algorithm for identifying Condorcet team in noisy comparisons.
problem Online learning with noisy comparisons of teams.
method Formalized dueling teams problem, developed algorithms for stochastic and deterministic settings.
result Identifies Condorcet winning team with reduced number of duels.
This work focuses on dynamic regret of online convex optimization that compares the performance of online learning to a clairvoyant who knows the sequence of loss functions in advance and hence selects the minimizer of the loss function at each step. By assuming that the clairvoyant moves slowly (i.e., the minimizers c…
We present and study models of adversarial online learning where the feedback observed by the learner is noisy, and the feedback is either full information feedback or bandit feedback. Specifically, we consider binary losses xored with the noise, which is a Bernoulli random variable. We consider both a constant noise r…
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
New method clusters items with bandit feedback without parametric assumptions.
problem Clustering with noisy observations from unknown distributions.
method Kernel-based approach to nonparametric clustering with bandit feedback.
result Adaptive algorithm with theoretical guarantees for unknown signal-to-noise ratio.
PCTS optimizes noisy, delayed, multi-fidelity feedbacks in black-box optimization.
problem Optimizing unknown functions with noisy, delayed, and multi-fidelity feedbacks.
method ProCrastinated Tree Search (PCTS) with DUCB1 and DUCBV algorithms.
result PCTS achieves better regret bounds for delayed, noisy, and multi-fidelity feedbacks.
Paper proposes DG-ETC for online submodular maximization with stochastic bandit feedback.
problem Online unconstrained submodular maximization with stochastic bandit feedback.
method Double-Greedy - Explore-then-Commit (DG-ETC) approach.
result DG-ETC achieves logarithmic regret O ( d log ( d T ) ) O(d\log(dT)) O ( d log ( d T )) for 1 / 2 1/2 1/2 -approximate pseudo-regret. Study quantile reward identification with 1-bit feedback constraints.
problem Best arm identification with quantile reward and 1-bit communication.
method Proposes an algorithm using noisy binary search for quantile reward estimation.
result Derives upper and lower bounds on sample complexity for 1-bit feedback.
Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedb…
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
The paper tackles efficient change point detection with limited samples.
problem Identifying multiple change points with minimal queries in noisy environments.
method Adaptive algorithm that first detects likely change points and refines their locations.
result The sample complexity is jointly governed by jump magnitudes and change point positions.
Algorithm clusters items by sequentially selecting features, minimizing observations.
problem Clustering items based on bandit feedback with many features.
method Sequential Halving algorithm for feature selection.
result Accurate recovery of item partition with minimal observations.
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and …
Algorithm minimizes regret in dueling bandits with contextualized utilities.
problem Minimizing regret in dueling bandits with context-dependent utilities.
method Proposes CoLSTIM algorithm based on perturbed utility estimates.
result Achieves regret of order i l d e O ( d T ) ilde O(\sqrt{dT}) i l d e O ( d T ) . We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observ…
New algorithm improves game learning with randomised optimism.
problem Learning in matrix games with unknown payoffs and bandit feedback.
method Integrates evolutionary algorithms into bandit framework for randomised optimism.
result Achieves sublinear regret, outperforming classical methods.
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
Reduces user feedback needed for accurate recommender systems.
problem Limited user feedback in recommender systems.
method Partial Bandit and Semi-Bandit approach for efficient user feedback retrieval.
result Similar global accuracy and learning efficiency with reduced feedback.
Unified framework for expert selection with bandit and lower-bound feedback.
problem Selecting the best expert in scenarios with bandit feedback and lower-bound information.
method Introduces a new feedback model combining bandit and lower-bound information, proving optimal regret bounds for modified Exp3 algorithms.
result Optimal regret bounds for modified Exp3 algorithms, generalizing both bandit and full-information settings.
Study online multiclass classification under bandit feedback, extending previous results.
problem Online multiclass classification with bandit feedback, focusing on label space unboundedness.
method Extend Daniely and Helbertal's results, show necessity and sufficiency of Bandit Littlestone dimension for learnability.
result Sequential uniform convergence is necessary but not sufficient for bandit online learnability.
DisCor corrects reinforcement learning issues by re-weighting collected data.
problem Reinforcement learning algorithms struggle with instability and sensitivity to hyperparameters.
method DisCor reweights collected data to mitigate issues caused by the distribution of experience.
result DisCor improves reinforcement learning in challenging settings like multi-task learning and noisy reward signals.
New algorithm optimizes noisy, potentially corrupted functions.
problem Optimizing unknown functions with noisy bandit feedback, especially when evaluations are corrupted.
method Fast-Slow GP-UCB algorithm, combining robust and non-robust evaluations, enlarged confidence bounds.
result Theoretical analysis upper bounds cumulative regret, showing dependencies on corruption level and kernel.
New method uses correlated auxiliary feedback to reduce regret in parameterized bandits.
problem Reducing regret in parameterized bandits with correlated auxiliary feedback.
method Develops a reward estimator using auxiliary feedback with tight confidence bounds.
result Shows significant reduction in regret compared to standard methods.
We use online convex optimization (OCO) for setpoint tracking with uncertain, flexible loads. We consider full feedback from the loads, bandit feedback, and two intermediate types of feedback: partial bandit where a subset of the loads are individually observed and the rest are observed in aggregate, and Bernoulli feed…
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.
Banker-OMD improves online learning with delayed feedback.
problem Handling delayed feedback in online learning.
method Generalized Online Mirror Descent (OMD) framework.
result Achieves nearly-optimal performance in three bandit scenarios.
Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. New framework tackles submodular welfare with multi-agent combinatorial bandits.
problem Maximizing total welfare among agents with shared constraints and submodular utilities under bandit feedback.
method Proposes an explore-then-commit strategy with randomized assignments for multi-agent combinatorial bandits.
result Achieves i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) regret, first for partition-based submodular welfare problem under bandit feedback. One-bit feedback suffices for a bandit problem's optimal strategy.
problem Optimal strategy for multi-armed bandit problem with limited feedback.
method Coding and decoding schemes for one-bit feedback to mimic full-reward feedback.
result Regret ratio approaches 1 with one-bit feedback.
New algorithms handle online prediction with bandit and delayed feedback, improving regret bounds.
problem Achieving finite bounds on surrogate regret with limited feedback.
method Proposed algorithms for bandit and delayed feedback, including inverse-weighted gradient and pseudo-inverse matrix estimators.
result Achieved improved surrogate regret bounds of O ( K T ) O(\sqrt{KT}) O ( K T ) and O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) . New RL algorithm optimizes policies with bandit feedback, matching previous bounds.
problem Optimizing policies with unknown transitions and bandit feedback.
method Optimistic Trust Region Policy Optimization (TRPO) algorithm.
result Sub-linear regret bounds for both stochastic and adversarial rewards.
New algorithm reduces regret in delayed feedback generalised linear bandits.
problem Regret in delayed feedback generalised linear bandits.
method Adaptation of optimistic algorithm to delayed feedback.
result Achieves a regret bound independent of the horizon's delay penalty.
New algorithms ensure fair selection in combinatorial semi-bandit with unrestricted delays.
problem Fair selection in stochastic combinatorial semi-bandit with delayed feedback.
method Introduced merit-based fairness constraints and new bandit algorithms for reward and fairness.
result Achieved sublinear expected reward and fairness regrets with dependence on delay distribution quantiles.
New algorithms tackle adversarial combinatorial bandits with switching costs.
problem Adversarial combinatorial bandits with switching costs.
method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.
result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.
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,…
We present online boosting algorithms for multiclass classification with bandit feedback, where the learner only receives feedback about the correctness of its prediction. We propose an unbiased estimate of the loss using a randomized prediction, allowing the model to update its weak learners with limited information. …