New algorithms for best arm identification in delayed feedback MABs.
problem Best arm identification in multi-armed bandits with delayed feedback.
method Generalized framework for modeling partial and delayed feedback, efficient algorithms for biased and unbiased estimators, and parallel MAB extensions.
result Exploiting partial feedback can lead to significant improvements over baselines in sequential and parallel MAB settings.
Graph-based feedback improves bandit algorithms' performance.
problem Stochastic multi-armed bandit problem with graph feedback.
method Analysis of Thompson Sampling and UCB algorithms in graph-based feedback setting.
result Regret bounds that combine graph structure and arm means gaps.
Develops hedging algorithm for online expert weight allocation with delayed feedback.
problem Adaptive hedging strategies for online expert weight allocation with delayed feedback.
method General Hedging algorithm G \mathcal{G} G based on exponential reweighing of experts' losses. result Proves adversarial loss bounds for the General Hedging algorithm G \mathcal{G} G in the delayed feedback setting. New algorithm for recommending best arms with aggregated feedback.
problem Finding the best arm under aggregated feedback when precise rewards are unavailable.
method Gaussian Process Optimistic Optimisation (GPOO) algorithm with adaptive tree construction.
result The proposed algorithm achieves new simple regret bounds with aggregated feedback.
New algorithm for dueling bandits with qualitative feedback outperforms existing methods.
problem Qualitative feedback in dueling bandits.
method Direct algorithms using qualitative feedback probabilities.
result Proposed algorithms significantly outperform existing DB algorithms.
Paper characterizes minimax regret rates for online ranking with top-k feedback.
problem Analyzing online ranking with partial feedback.
method Developed techniques from partial monitoring to characterize minimax regret rates.
result Full characterization of minimax regret rates for Precision@n.
Unified framework for analyzing online convex optimization across various settings.
problem Analyzing online convex optimization in different settings and feedback types.
method Unified framework allowing systematic proposal and analysis of meta-algorithms.
result Comparable regret bounds for various feedback types and adversary types.
We investigate contextual online learning with nonparametric (Lipschitz) comparison classes under different assumptions on losses and feedback information. For full information feedback and Lipschitz losses, we design the first explicit algorithm achieving the minimax regret rate (up to log factors). In a partial feedb…
New algorithm for linear bandits learns from feature feedback, reducing regret.
problem Linear bandit problem with feature feedback.
method Developed new theory and algorithms for linear bandits with feature feedback.
result Achieves regret scaling like k T k\sqrt{T} k T , improving over traditional linear bandits. The paper tackles combinatorial pure exploration with various feedback structures and proposes efficient algorithms.
problem Identifying the optimal action in a combinatorial space with limited feedback and nonlinear rewards.
method Designs polynomial-time adaptive algorithms for CPE-BL and CPE-PL, providing sample complexity analyses.
result The proposed algorithms achieve sample complexity close to lower bounds and outperform existing methods.
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 ) . CAFL breaks feedback loops in recommender systems using causal inference.
problem Feedback loops in recommender systems compromise recommendation quality and homogenize user behavior.
method Causal Adjustment for Feedback Loops (CAFL) algorithm that breaks feedback loops using causal inference.
result CAFL improves recommendation quality compared to prior correction methods.
Online boosting for multiclass classification with limited feedback.
problem Online multiclass classification with bandit feedback.
method Proposed unbiased loss estimate and extended full information boosting algorithms to bandit setting.
result Asymptotic error bounds match full information counterparts, with larger sample complexity due to limited feedback.
New Q-learning algorithms reduce regret in inventory control problems.
problem Efficiently learning optimal policies in inventory control problems with limited feedback.
method Proposed Elimination-Based Half-Q-Learning (HQL) and Full-Q-Learning (FQL) algorithms with theoretical regret bounds.
result HQL incurs i l d e O ( H 3 T ) ilde{\mathcal{O}}(H^3\sqrt{ T}) i l d e O ( H 3 T ) regret, FQL incurs i l d e O ( H 2 T ) ilde{\mathcal{O}}(H^2\sqrt{ T}) i l d e O ( H 2 T ) regret, independent of state and action space sizes. 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 avoid weight transport, outperforming current deep learning methods.
problem Current deep learning algorithms rely on weight transport, which is biologically implausible.
method Two mechanisms: weight mirror and modified Kolen-Pollack algorithm, using random feedback weights.
result These mechanisms outperform feedback alignment and other methods on visual recognition tasks.
Study of reinforcement learning with additional feedback observations.
problem Episodic reinforcement learning in Markov decision processes with feedback observations.
method Formalization of feedback graph, model-based algorithms leveraging feedback, regret bound analysis.
result Regret bound depends only on the size of the maximum acyclic subgraph of the feedback graph.
New MAB problem with delayed, anonymous feedback analyzed.
problem Delayed, anonymous feedback in stochastic bandits.
method Phase-based extensions of UCB algorithm for SDCAF.
result Sub-linear regret guarantees for proposed algorithms.
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.
New method learns from either positive or negative feedback alone.
problem Limited applicability of existing preference optimization methods in scenarios with only unpaired feedback.
method Decouples learning from positive and negative feedback, using expectation-maximization (EM) to optimize probability of positive outcomes and explicitly incorporate negative examples.
result Stable learning from negative feedback alone demonstrated.
Online boosting for multilabel ranking with limited feedback.
problem Multilabel ranking with top-k feedback.
method Surrogate loss function and unbiased estimator for weak learners.
result Adapted full information multilabel ranking algorithms to top-k feedback setting with theoretical and experimental support.
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.
Conversational UCB accelerates bandit learning with user feedback.
problem Slow learning speed in traditional contextual bandit algorithms.
method Generalized contextual bandit to conversational contextual bandit, leveraging both behavioral and conversational feedbacks.
result ConUCB achieves a smaller regret upper bound, indicating faster learning speed.
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.
Reinforcement learning with trajectory feedback instead of state-action rewards.
problem Frequent feedback not available in practice.
method Extended reinforcement learning algorithms using trajectory feedback for known and unknown transition models.
result Hybrid optimistic-Thompson Sampling algorithm for unknown transition models.
Algorithm improves query recommendations with immediate user feedback.
problem Lack of adaptability to immediate user feedback in query recommendation algorithms.
method Augmented transformer-based causal language models with multi-armed bandit framework.
result Substantial improvement in per-round regret compared to state-of-the-art models.
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.
Adaptive MAB algorithms handle composite, anonymous feedback without reward interval knowledge.
problem Multi-armed bandit with composite and anonymous feedback, especially without reward interval size knowledge.
method Proposed adaptive algorithms for stochastic and adversarial cases, without reward interval knowledge.
result First algorithm for adversarial case handling non-oblivious adversary and unknown reward interval size.
We study an online decision making problem where on each round a learner chooses a list of items based on some side information, receives a scalar feedback value for each individual item, and a reward that is linearly related to this feedback. These problems, known as contextual semibandits, arise in crowdsourcing, rec…
New algorithm improves bandit with graph feedback by decomposing regret.
problem Improving performance in bandit problems with graph feedback.
method Partition-based algorithm framework using regret decomposition.
result Improved and optimal regret bounds on various graph families.
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.
New algorithms minimize regret in combinatorial online learning with relative feedback.
problem Minimizing regret in online learning with subset-wise relative preference feedback.
method Instance-dependent and order-optimal regret algorithms for two settings: bounded size subsets and fixed size subsets.
result Regret bounds of O ( n m ln T ) O(\frac{n}{m} \ln T) O ( m n ln T ) and O ( n k ln T ) O(\frac{n}{k} \ln T) O ( k n ln T ) for respective settings. Safe RL with binary feedback using SABRE algorithm.
problem Safe reinforcement learning with binary safety feedback.
method SABRE algorithm, combining active learning and reinforcement learning.
result Provable safe policy with high probability, no unsafe actions during training.
A new one-point feedback scheme improves ZO algorithms for black-box optimization.
problem Optimizing black-box functions without gradient information.
method Proposes a one-point feedback scheme to estimate gradients using residuals.
result Matches query complexity of two-point schemes for deterministic Lipschitz functions.
New algorithm minimizes expert selection regret in partial bandit feedback.
problem Minimizing expert selection regret in partial bandit feedback.
method Develops a sequential minimax optimal algorithm for a generalized partial monitoring setting.
result Second order regret bounds against a general expert selection sequence.
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 algorithms ensure fairness in sequential decisions, accounting for feedback effects.
problem Ignoring feedback effects can lead to unfair outcomes in sequential decision-making.
method Model feedback effects as MDPs and propose fair properties and algorithms.
result Demonstrated the necessity of considering dynamical effects for fairness.
Active learning framework for optimizing human preferences in reinforcement learning.
problem Selecting most informative feedback for training models of human preferences.
method Proposes an active learning framework to collect preferential feedback online or offline.
result Errors in DPO logit estimates diminish with more feedback.
Novel algorithms for online learning with uncertain feedback graphs reduce regret.
problem Uncertainty in feedback graphs hinders traditional online learning approaches.
method Developed novel online learning algorithms to handle uncertain feedback graphs.
result Proved sublinear regret under mild conditions for the proposed algorithms.
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.
Test for linearizing 2-input systems with 2D feedback.
problem Linearizability of two-input systems by feedback.
method Algorithmic test for 2D endogenous feedback.
result Systematic derivation of flat outputs.
Online learning with delayed feedback has received increasing attention recently due to its several applications in distributed, web-based learning problems. In this paper we provide a systematic study of the topic, and analyze the effect of delay on the regret of online learning algorithms. Somewhat surprisingly, it t…
Estimates mode from partial feedback, improving AI learning pipelines.
problem Estimating the mode of a distribution with partial feedback.
method Entropy coding, coarse sufficient statistics, bandit algorithms.
result Statistically and computationally efficient solution to mode estimation.
First sample-efficient algorithm for learning EFCE in bandit feedback settings.
problem Learning EFCE in bandit feedback settings for IIEFGs.
method Proposed K K K -EFCE and uncoupled no-regret algorithm with wide-range regret minimization. result First sample-efficient algorithm for learning EFCE from bandit feedback.
Algorithm minimizes regret in predictive models influenced by their own predictions.
problem Finding near-optimal models under performativity with unknown shifts.
method Developed an algorithm that uses performative feedback to achieve low regret, scaling only with distribution shift complexity.
result Achieved regret bounds scaling with distribution shift complexity, not reward function complexity.
Error feedback improves sign-based gradient compression algorithms.
problem Sign-based gradient compression algorithms fail to converge optimally and generalize poorly.
method Integrating error feedback into the gradient compression process.
result EF-SGD achieves the same convergence rate as SGD without additional assumptions.
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.
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.