Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with O ( log log T ) O(\log\log T) O ( log log T ) oracle queries for worst-case linear rewards. Study improves CTS's approximation regret for combinatorial bandits.
problem Improving CTS's performance on non-exact oracles.
method Develops a new O ( log ( T ) / Δ ) \mathcal{O}(\log(T)/Δ) O ( log ( T ) /Δ ) upper bound for CTS under specific conditions. result First O ( log ( T ) / Δ ) \mathcal{O}(\log(T)/Δ) O ( log ( T ) /Δ ) approximation regret upper bound for CTS. Algorithm solves online binary classification and infinite games using ERM oracle.
problem Online learning and solving infinite games with computationally inefficient oracles.
method Proposes an algorithm relying solely on ERM oracle calls for online binary classification and nonparametric games.
result Achieves finite and sublinearly growing regret in various settings.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.
New algorithm tackles smooth online learning with optimal regret.
problem Smoothed online learning with adversarial distributions.
method Oracle-efficient algorithms for nonparametric function classes.
result Oracle-efficient algorithms achieve optimal regret bounds.
Adapts to misspecification in contextual bandits using offline regression.
problem Unexpected regret due to misspecified reward models.
method Adapts to misspecification by reverting to a safe policy when necessary.
result Regret guarantees degrade gracefully with misspecification level.
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
New algorithms achieve small prediction regret for learning from overlapping groups.
problem Online multi-group learning with fairness applications.
method Oracle-efficient algorithms for groups not explicitly enumerated.
result Sublinear regret in various settings.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require only poly-logarithmically many calls to the approximation oracle per it…
We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a Bayesian and a frequentist regret bound respectively, both of which reduce to the near-optimal bound …
New algorithm learns FMDP structure while minimizing regret.
problem Regret minimization in FMDPs with unknown structure.
method Optimism in face of uncertainty principle combined with statistical structure learning.
result First algorithm to learn FMDP structure while minimizing regret.
Paper tackles online learning on curved spaces without projections.
problem Online learning on Riemannian manifolds with computational constraints.
method Develops projection-free algorithms for geodesically convex optimization.
result Achieves sub-linear regret guarantees in online geodesically convex optimization.
New method tackles endogeneity in online learning with improved regret bounds.
problem Endogeneity in real data due to omitted variables, strategic behaviors, etc.
method O2SLS (Online Two-Stage Least Squares) for Instrumental Variable (IV) regression.
result O2SLS achieves identification and oracle regret bounds for stochastic online learning.
Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O ( T 2 3 ( K log ( ∣ Π ∣ ) ) 1 3 ) O(T^{\frac{2}{3}}(K\log(|Π|))^{\frac{1}{3}}) O ( T 3 2 ( K log ( ∣Π∣ ) ) 3 1 ) regret bound. result First to improve regret bound and match original bound for stochastic case.
We propose the Generalized Policy Elimination (GPE) algorithm, an oracle-efficient contextual bandit (CB) algorithm inspired by the Policy Elimination algorithm of \cite{dudik2011}. We prove the first regret optimality guarantee theorem for an oracle-efficient CB algorithm competing against a nonparametric class with i…
OE2D framework reduces contextual bandits to offline regression for near-optimal regret.
problem Efficiently learning contextual bandits with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that reduces contextual bandits to offline regression.
result Near-optimal regret for contextual bandits with large action spaces and O ( log T ) O(\log T) O ( log T ) calls to an offline regression oracle. Framework reduces contextual bandit learning to offline regression with near-optimal regret.
problem Efficient learning with large action spaces and complex reward functions.
method Offline Estimation to Decisions (OE2D) algorithm that minimizes regret with near-optimal oracle calls.
result Near-optimal regret for contextual bandits with large action spaces and O ( l o g ( T ) ) O(log(T)) O ( l o g ( T )) offline oracle calls. Algorithm minimizes regret while adhering to unknown safety constraints.
problem Online learning with unknown safety constraints.
method General meta-algorithm leveraging online regression and learning oracles.
result Concrete algorithm with T \sqrt{T} T regret for linear constraints. New algorithm reduces regret in online learning for piecewise continuous functions.
problem Exponential loss in efficiency when moving from classical to adversarial learning.
method Introduces generalized bracketing numbers and Follow-the-Perturbed-Leader algorithm.
result Optimal scaling of optimization oracle calls with average regret.
Oracle-efficient algorithms for online learning with smoothed and hint-adversaries.
problem Online learning with beyond worst-case adversaries.
method Oracle-efficient algorithms for two settings: smoothed analysis and K K K -hint transductive learning. result Oracle-efficient regret bounds for learning real-valued and binary-valued functions.
Neural- σ 2 σ^2 σ 2 -LinearUCB improves regret in neural contextual bandits.
problem Balancing exploration and exploitation in neural contextual bandits.
method Proposes a variance-aware neural UCB algorithm using neural representations and an upper bound of reward noise variance.
result Oracle and practical versions of Neural- σ 2 σ^2 σ 2 -LinearUCB achieve better regret guarantees and performance. Improved FTPL algorithm reduces regret in predictable minimax games.
problem Online learning and minimax games with predictable loss sequences.
method Optimistic modification of FTPL with dual regularization view.
result Tighter regret bounds for predictable sequences, O ( T − 1 / 2 ) O(T^{-1/2}) O ( T − 1/2 ) accuracy. We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and h…
The paper addresses contextual optimization problems with feedback, aiming to minimize regret.
problem Contextual optimization with feedback information.
method Characterizing the optimal minimax policy in offline setting and leveraging geometric characterization in online setting to optimize cumulative regret.
result Developed an algorithm yielding logarithmic regret bound in the online setting.
PCGS-TF uses a Transformer to adaptively control expert switching in non-stationary environments.
problem Static regret is insufficient for strictly online prediction in non-stationary settings.
method Policy-Controlled Generalized Share (PCGS) with a Transformer as an update controller.
result PCGS-TF achieves the lowest dynamic regret in non-stationary families and expert pools.
New algorithm reduces regret bounds for Bayesian optimization with unknown hyperparameters.
problem Optimizing black-box functions with unknown hyperparameters, especially length scale.
method Length Scale Balancing (LB) - aggregating multiple surrogate models with varying length scales.
result LB achieves a regret bound only logaritically away from the oracle algorithm.
New algorithms adapt to model misspecification in contextual bandits.
problem Design efficient algorithms for contextual bandits that handle model misspecification gracefully.
method Oracle-efficient algorithms for ε-misspecified contextual bandits using square loss regression.
result First algorithm achieving optimal regret bound for unknown misspecification level in linear contextual bandits.
We revisit the challenge of designing online algorithms for the bandit convex optimization problem (BCO) which are also scalable to high dimensional problems. Hence, we consider algorithms that are \textit{projection-free}, i.e., based on the conditional gradient method whose only access to the feasible decision set, i…
Study on optimal rates for sequential probability assignment using smoothed analysis.
problem Optimal rates for sequential probability assignment under smoothed adversaries.
method General-purpose reduction from minimax rates to transductive learning, development of an efficient algorithm using MLE oracle.
result Optimal (logarithmic) fast rates for parametric and finite VC dimension classes, sublinear regret for general classes.
We study contextual linear bandit problems under feature uncertainty, where the features are noisy and have missing entries. To address the challenges posed by this noise, we analyze Bayesian oracles given the observed noisy features. Our Bayesian analysis reveals that the optimal hypothesis can significantly deviate f…
New method improves CATE model selection with optimal regret rates.
problem Nontrivial task of selecting accurate CATE models.
method Causal Q-aggregation using doubly robust loss.
result Achieves optimal oracle model selection regret rates of log(M)/n.
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 algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
Study analyzes broker's gain from trade in repeated context-based trading.
problem Maximizing traders' net utility in repeated context-based brokerage.
method Proposes algorithms achieving tight regret bounds in full and limited feedback settings.
result Achieves tight 1/2-approximation result for gain from trade.
New algorithms improve contextual bandit performance by adapting to problem difficulty.
problem Improving contextual bandit performance on problems with varying difficulty.
method Introducing complexity measures and oracle-efficient algorithms.
result Achieves optimal instance-dependent regret bounds for rich policy classes.
Optimizes nonconvex optimization by converting it to static regret minimization.
problem Nonconvex optimization challenges in machine learning.
method Black-box online-to-nonconvex conversion with static regret minimization oracles.
result Achieves optimal convergence rates for nonconvex optimization.
Study on tradeoffs between mistakes and ERM oracle calls in online and transductive learning.
problem Analyzing online and transductive learning with limited ERM and weak consistency oracle access.
method Proves lower bounds and upper bounds on mistakes and oracle calls, considering realizable and agnostic cases.
result Achieves optimal mistake bounds with weak consistency queries for certain concept classes.
Adaptive algorithm reduces regret in causal bandits.
problem Minimize regret in causal bandits with unknown d-separators.
method Adaptive algorithm exploiting d-separators without prior knowledge.
result Significantly smaller regret than previous methods.
Faster algorithm reduces contextual bandit regret with fewer offline regression calls.
problem Optimizing reward in contextual bandits with unknown functions.
method Designing a simple algorithm with O ( log T ) {O}(\log T) O ( log T ) offline regression calls. result Achieves statistically optimal regret with minimal offline calls.
Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
Thompson Sampling tackles noisy context in stochastic bandits.
problem Designing an action policy for noisy, corrupted contexts in stochastic bandits.
method Introducing a Thompson Sampling algorithm for Gaussian bandits with Gaussian context noise, adopting an information-theoretic analysis.
result Demonstrates the Bayesian regret of the proposed algorithm concerning the oracle's action policy.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.
Study efficient resource allocation for detecting extreme values.
problem Efficiently allocate limited resources to detect extreme values in various fields.
method Proposes ExtremeHunter algorithm for sequential resource allocation under limited feedback.
result Demonstrates ExtremeHunter outperforms oracle policy in detecting extreme values.
A major challenge in contextual bandits is to design general-purpose algorithms that are both practically useful and theoretically well-founded. We present a new technique that has the empirical and computational advantages of realizability-based approaches combined with the flexibility of agnostic methods. Our algorit…
New study reveals a polynomial penalty for adapting to unknown margin parameters in batched nonparametric bandits.
problem Adapting to an unknown margin parameter in batched nonparametric bandits.
method Introduces the regret inflation criterion and develops RoBIN algorithm to achieve optimal regret inflation.
result The optimal regret inflation grows polynomially with the horizon T, characterized by a convex optimization problem.
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.
This paper tackles bandit optimization with a new pairwise comparison oracle for unknown strongly concave functions.
problem Maximizing an unknown strongly concave function over T periods with a biased pairwise comparison oracle.
method Introduced a discretization technique and local polynomial approximation to relate the problem to linear bandits. Developed a tournament successive elimination technique to localize the discretized cell and run LinUCB algorithm on cells.
result Established optimal regret bounds and improved state-of-the-art results in operations management problems.