Online Learning with Sublinear Best-Action Queries

• URL: http://arxiv.org/abs/2407.16355v1
• Date: Tue, 23 Jul 2024 09:59:43 GMT
• Title: Online Learning with Sublinear Best-Action Queries
• Abstract summary: We study the power of emphbest-action queries, which reveal beforehand the identity of the best action at a given time step. We prove that in the full feedback model, $k$ queries are enough to achieve an optimal regret of $Thetaleft(minleftsqrt T, frac Tkrightright)$.
• Score: 15.625072719419727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In online learning, a decision maker repeatedly selects one of a set of actions, with the goal of minimizing the overall loss incurred. Following the recent line of research on algorithms endowed with additional predictive features, we revisit this problem by allowing the decision maker to acquire additional information on the actions to be selected. In particular, we study the power of \emph{best-action queries}, which reveal beforehand the identity of the best action at a given time step. In practice, predictive features may be expensive, so we allow the decision maker to issue at most $k$ such queries. We establish tight bounds on the performance any algorithm can achieve when given access to $k$ best-action queries for different types of feedback models. In particular, we prove that in the full feedback model, $k$ queries are enough to achieve an optimal regret of $\Theta\left(\min\left\{\sqrt T, \frac Tk\right\}\right)$. This finding highlights the significant multiplicative advantage in the regret rate achievable with even a modest (sublinear) number $k \in \Omega(\sqrt{T})$ of queries. Additionally, we study the challenging setting in which the only available feedback is obtained during the time steps corresponding to the $k$ best-action queries. There, we provide a tight regret rate of $\Theta\left(\min\left\{\frac{T}{\sqrt k},\frac{T^2}{k^2}\right\}\right)$, which improves over the standard $\Theta\left(\frac{T}{\sqrt k}\right)$ regret rate for label efficient prediction for $k \in \Omega(T^{2/3})$.

Related papers

• Online Learning with LLM Experts from Limited Feedback [91.92265248492875]
  We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback.<n>We propose algorithms that strategically select and observe rewards to minimize regret.
  arXiv  Detail & Related papers  (2026-09-05T02:30:59Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets [27.973926244529267]
  We study adversarial inverse linear optimization known as contextual recommendation.<n>The learner learner regret achieves this by combining a characterization of optimal solutions on M- sets with a volume argument.
  arXiv  Detail & Related papers  (2026-02-02T05:48:54Z)
• Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints [8.314956969778692]
  We study an online learning problem with long-term budget constraints in the adversarial setting.<n>In this problem, at each round $t$, a learner selects an action from a convex set, after which an adversary reveals a cost function.<n>Our approach yields an efficient solution for the $textttAdversas$ problem with improved guarantees.
  arXiv  Detail & Related papers  (2025-08-23T11:21:24Z)
• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  We study online learning with oblivious losses delays under a novel clairvoyance'' that limits how many past rounds can be tracked simultaneously for delayed feedback. Our algorithms achieve mini-optimal regret across all capacity levels, with performance gracefully under suboptimal capacity.
  arXiv  Detail & Related papers  (2025-03-25T17:20:39Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  We define an online learning and optimization problem with discrete and irreversible decisions contributing toward a coverage target.<n>In each period, a decision-maker selects facilities to open, receives information on the success of each one, and updates a classification model to guide future decisions.<n>The goal is to minimize facility openings under a chance constraint reflecting the coverage target, in an horizon regime characterized by a large target number of facilities.
  arXiv  Detail & Related papers  (2024-06-20T23:00:25Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM) We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  We show a problem where the unknown reward $g(gamma, v)$ depends on the proposed threshold $gamma$ and latent value $v$ and it can be $only$ achieved if the threshold is lower than or equal to the unknown latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring.
  arXiv  Detail & Related papers  (2023-12-07T19:30:08Z)
• Contextual Bandits and Imitation Learning via Preference-Based Active Queries [17.73844193143454]
  We consider the problem of contextual bandits and imitation learning, where the learner lacks direct knowledge of the executed action's reward. Instead, the learner can actively query an expert at each round to compare two actions and receive noisy preference feedback. The learner's objective is two-fold: to minimize the regret associated with the executed actions, while simultaneously, minimizing the number of comparison queries made to the expert.
  arXiv  Detail & Related papers  (2023-07-24T16:36:04Z)
• From Adaptive Query Release to Machine Unlearning [34.25760971846068]
  We formalize the problem of machine unlearning as design of efficient unlearning algorithms corresponding to learning algorithms. We show that unlearning in convex optimization (SCO) can be reduced to the above, yielding improved guarantees for the problem.
  arXiv  Detail & Related papers  (2023-07-20T20:46:39Z)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  We investigate non-stationary projection-free online learning, and choose dynamic regret and adaptive regret to measure the performance. Our results are the first general-case dynamic regret bounds for projection-free online learning, and can recover the existing $mathcalO(T3/4)$ static regret. We propose a projection-free method to attain an $tildemathcalO(tau3/4)$ adaptive regret bound for any interval with length $tau.
  arXiv  Detail & Related papers  (2023-05-19T15:02:10Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  We study the $K$ contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes emphpreference-based feedback suggesting that one decision was better than the other. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works.
  arXiv  Detail & Related papers  (2021-11-24T07:14:57Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  We study the optimal batch-regret tradeoff for batch linear contextual bandits. We prove its regret guarantee, which features a two-phase expression as the time horizon $T$ grows. We also prove a new matrix inequality concentration with dependence on their dynamic upper bounds.
  arXiv  Detail & Related papers  (2021-10-15T12:32:33Z)
• Pure Exploration with Structured Preference Feedback [25.894827160719526]
  We consider the problem of pure exploration with subset-wise preference feedback, which contains $N$ arms with features. We present two algorithms that guarantee the detection of the best-arm in $tildeO (fracd2K Delta2)$ samples with probability at least $1.
  arXiv  Detail & Related papers  (2021-04-12T08:57:29Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  We consider a sequential assortment selection problem where the user choice is given by a multinomial logit (MNL) choice model whose parameters are unknown. We propose upper confidence bound based algorithms for this MNL contextual bandit. We show that a simple variant of the algorithm achieves the optimal regret for a broad class of important applications.
  arXiv  Detail & Related papers  (2021-03-25T15:42:25Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  We introduce the problem of online convex optimization with continuous switching constraint. We show that, for strongly convex functions, the regret bound can be improved to $O(log T)$ for $S=Omega(log T)$, and $O(minT/exp(S)+S,T)$ for $S=O(log T)$.
  arXiv  Detail & Related papers  (2021-03-21T11:43:35Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback. We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode. We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-02-17T18:54:08Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  We develop algorithms and nearly matching lower bounds for online learning with imperfect directional hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case.
  arXiv  Detail & Related papers  (2020-02-11T23:06:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.