New trade-off found in bandit problems with unknown range.
problem Stochastic bandit problems with unknown range.
method Exhibit a strategy achieving new trade-off between distribution-dependent and distribution-free regret bounds.
result Achieves the rates for regret indicated by the new trade-off.
Study minimax regret in bilateral trade with heavy-tailed valuations.
problem Minimizing regret in bilateral trade with infinite variance valuations.
method Extended self-bounding property, truncated-mean estimation, epoch-based algorithm.
result Achieves regret bound of O ( T 1 − 2 β ( p − 1 ) / ( β p + d ( p − 1 ) ) ) O(T^{1-2β(p-1)/(βp + d(p-1))}) O ( T 1 − 2 β ( p − 1 ) / ( β p + d ( p − 1 )) ) under specific conditions. Recursive least-squares algorithms often use forgetting factors as a heuristic to adapt to non-stationary data streams. The first contribution of this paper rigorously characterizes the effect of forgetting factors for a class of online Newton algorithms. For exp-concave and strongly convex objectives, the algorithms a…
Brokerage algorithm learns from context to minimize trading regret.
problem Minimizing trading regret in a sequential brokerage problem.
method Design of algorithms with optimal theoretical regret guarantees.
result Optimal theoretical regret guarantees under various assumptions.
The paper analyzes regret in bilateral trade mechanisms without prior valuations.
problem Designing efficient trade mechanisms without prior knowledge of valuations.
method Regret minimization framework over rounds of interactions with no prior knowledge of valuations.
result Characterization of regret bounds for different feedback models and valuations.
The paper explores trade-offs between regret and variance in online learning algorithms.
problem Investigating the trade-offs between regret and variance in online learning.
method Analysis of the Exponentially Weighted Average (EWA) algorithm and its variants.
result A variant of EWA either achieves negative regret or guarantees a logarithmic bound on both variance and regret.
Survey of universal portfolio techniques for minimizing investment regret.
problem Minimizing investment regret in algorithmic trading.
method Explains various universal portfolio techniques and their proofs.
result Coverage of fundamental concepts and algorithms in regret minimization.
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.
Unified framework for distributional regret in bandits and reinforcement learning.
problem Characterizing the distribution of regret in multi-armed bandits and reinforcement learning.
method Unified framework with a UCBVI-style algorithm and distributional regret bounds.
result Distributional regret bounds with optimal trade-offs between expected and distributional regret.
FPML algorithm reduces regret by limiting the number of arms chosen per round.
problem Adversarial online learning with resource budget constraints.
method Follow the Perturbed Multiple Leaders (FPML) algorithm.
result Achieves expected regret O ( T 1 B + 1 ln ( N ) B B + 1 ) \mathcal{O}(T^{\frac{1}{B+1}}\ln(N)^{\frac{B}{B+1}}) O ( T B + 1 1 ln ( N ) B + 1 B ) . Maximizing trading volume in online learning framework between traders.
problem Maximizing the total number of trades between traders with unknown valuations.
method Developed algorithms for brokers to maximize trading volume under different feedback scenarios.
result Achieved logarithmic and poly-logarithmic regret rates for different feedback models.
Two new algorithms reduce online kernel regression's computational cost while maintaining optimal regret bounds.
problem Trade-off between regret and computational cost in online kernel regression.
method AOGD-ALD and NONS-ALD algorithms dynamically maintain nearly orthogonal basis to approximate kernel mapping and control approximate error.
result Achieves nearly optimal regret bounds at sublinear computational complexity.
New algorithm reduces memory-regret trade-off for bandits.
problem Optimizing memory usage in stochastic multi-armed bandits.
method Designing an algorithm with specific regret bound and proving lower bound.
result Optimal regret characterization in terms of memory and rounds.
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
Bayesian framework learns latent preference archetypes for many-objective optimization.
problem Expanding space of trade-offs and context-dependent human values.
method Dirichlet-process mixture model for latent preference archetypes, hybrid queries for efficient information.
result Mixture-aware Bayesian optimization outperforms standard methods on synthetic and real-world benchmarks.
Optimizes regret distribution in stochastic bandits for risk balance.
problem Balancing regret expectation and tail risk in stochastic bandits.
method Characterizes optimal regret tail probability for any threshold, proposes new policies.
result Discovers an intrinsic gap in optimal tail rate based on time horizon uncertainty.
We consider recommendation systems that need to operate under wireless bandwidth constraints, measured as number of broadcast transmissions, and demonstrate a (tight for some instances) tradeoff between regret and bandwidth for two scenarios: the case of multi-armed bandit with context, and the case where there is a la…
The paper tackles adaptive policy selection to maximize social welfare, achieving optimal regret bounds.
problem Maximizing social welfare through adaptive policy selection, considering both private utility and public revenue.
method The approach involves learning response functions through experimentation, deriving lower and upper bounds for regret, and using algorithms like Exp3.
result The algorithm achieves optimal regret bounds, showing that welfare maximization is harder than multi-armed bandit problems.
A new test improves statistical inference in bandit algorithms without sacrificing adaptiveness.
problem Challenges in statistical inference for adaptive randomised experiments in bandits.
method An allocation probability test for Thompson Sampling without trading-off regret or requiring large sample sizes.
result Improves statistical inference in small samples, showing advantages in mental health experiments.
Paper improves COCO problem, reducing constraint violation at the cost of slightly more regret.
problem Online Convex Optimization with adversarial constraints.
method Proposes new policies that trade off regret for reduced constraint violation.
result Achieves i l d e O ( d T + T β ) ilde{O}(\sqrt{dT}+ T^β) i l d e O ( d T + T β ) regret and i l d e O ( d T 1 − β ) ilde{O}(dT^{1-β}) i l d e O ( d T 1 − β ) CCV. New method identifies algo trading strategies as liquidity consumers or providers.
problem Determining if algo trading strategies consume or provide liquidity.
method Analyzes trade and price history to classify strategies as liquidity consumers or providers.
result Identifies net liquidity consumption or provision of algo trading strategies.
New method reduces GP bandit complexity while maintaining good performance.
problem Computational burden in Bayesian optimization with Gaussian processes.
method Information thresholding to compress GP posterior and reduce complexity.
result Sublinear regret bounds with sublinear posterior complexity.
Algorithm achieves optimal pricing with minimal exploration for dynamic markets.
problem Optimal pricing in dynamic markets with contextual information.
method Localized exploration-then-commit (LetC) algorithm with pure exploration, refinement, and exploitation stages.
result Achieves minimax optimal, dimension-free regret bound.
This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…
New algorithm offers costless model selection in contextual bandits.
problem Minimizing cumulative regret in stochastic contextual bandits.
method Gradually increasing class complexity and adapting to the simplest class with dominant estimation variance.
result Costless model selection is feasible under certain conditions, providing improved regret guarantees.
Study risk-sensitive reinforcement learning with Lipschitz dynamic risk measures, establishing regret bounds.
problem Risk-sensitive reinforcement learning in Markov decision processes.
method Two model-based algorithms for Lipschitz dynamic risk measures, focusing on regret bounds.
result Upper bounds demonstrate optimal dependencies on actions and episodes, reflecting risk sensitivity vs. sample complexity trade-off.
A new batch ensemble method reduces regret in stochastic bandits.
problem Efficiently balancing exploration and exploitation in online RL.
method Proposes a batch ensemble scheme to achieve near-optimal regret.
result Proves near-optimal regret with a single parameter independent of variance.
Proposes a method to learn policies from offline data with reduced bias.
problem Learning policies from offline data with reduced bias and complexity constraints.
method Cross-fitted debiasing device for policy learning from offline data.
result Achieves N \sqrt N N regret for complex policy classes with a product-of-errors nuisance remainder. New algorithms for batched dueling bandits with improved regret bounds.
problem Batched dueling bandits with noisy pairwise comparisons.
method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.
result Regret bounds match sequential bounds using only a logarithmic number of batches.
NeuralRBMLE tackles explore-exploit trade-offs in contextual bandits with neural networks.
problem Stochastic contextual bandit problem with general bounded reward functions.
method Reward-biased maximum likelihood estimation with neural networks to enforce exploration.
result Both NeuralRBMLE variants achieve O ~ ( T ) \widetilde{\mathcal{O}}(\sqrt{T}) O ( T ) regret. New algorithm reduces memory usage for multi-pass bandit problems.
problem Memory-efficient multi-pass bandit algorithms for large action spaces.
method Develops a B B B -pass algorithm with O ( 1 ) O(1) O ( 1 ) memory that achieves optimal regret. result Sharp memory-regret trade-off: O ( 1 ) O(1) O ( 1 ) memory suffices for Θ ( T 1 / 2 ) Θ(T^{1/2}) Θ ( T 1/2 ) regret in B B B passes. Unified framework for best arm identification and dueling bandits regret minimization.
problem Best arm identification and dueling bandits regret minimization.
method Tree-Guided Identify-Then-Exploit (TG-ITE) framework.
result Unified approach achieving optimal sample complexity and regret guarantees.
We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.
problem Establishing linear regret bounds for convex smooth losses.
method Constructing a convex smooth surrogate loss using Fenchel-Young losses generated by the convolutional negentropy.
result We derive a smooth loss with a linear surrogate regret bound.
New bandit algorithm works without realizability assumption.
problem Contextual bandit problems without realizability assumption.
method Computes a constrained regression problem in every epoch, ensuring similar regret guarantees as realizability-based algorithms.
result Ensures similar regret guarantees as realizability-based algorithms, up to a misspecification term.
Paper presents an algorithm for optimal regret in communicating Markov decision processes.
problem Achieving optimal regret in Markov decision processes with a communicating assumption.
method The algorithm explicitly tracks the constant K(M) to learn optimally, balancing exploration, co-exploration, and exploitation.
result The algorithm achieves asymptotically optimal regret K ( M ) log ( T ) + o ( log ( T ) ) K(M) \log(T) + \mathrm{o}(\log(T)) K ( M ) log ( T ) + o ( log ( T )) for communicating Markov decision processes. Study shows observing order book can significantly improve online market making performance.
problem Online market making with private valuations and limited feedback.
method Introduces action-dependent feedback model and proposes elimination-based and explore-then-perturb algorithms.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bounds with high probability in various settings. We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.…
Optimal algorithm for minimizing regret in heavy-tailed bandits.
problem Minimizing regret in stochastic multi-armed bandits with heavy-tailed distributions.
method Proposes an optimal algorithm under the assumption of uniformly bounded moments of order (1+ε).
result Matches the lower bound exactly in the first-order term and provides a finite-time bound on its regret.
Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of band…
New bounds for high-dimensional sparse linear bandits, balancing information and regret.
problem Stochastic linear bandits with high-dimensional sparse features.
method Derivation of minimax regret lower and upper bounds for explore-then-commit algorithm.
result Optimal rate of Θ ( n 2 / 3 ) Θ(n^{2/3}) Θ ( n 2/3 ) for data-poor regime, complemented by O ( n ) O(\sqrt{n}) O ( n ) under signal magnitude assumption. New algorithm reduces regret in online portfolio and quantum state learning.
problem Efficiently learning portfolios and quantum states online with minimal regret.
method BISONS algorithm for online portfolio selection, SCHRODINGER'S BISONS for quantum states, with polylogarithmic regret.
result First efficient algorithm with polylogarithmic regret for online portfolio selection and quantum states.
ALEXP improves model selection in linear bandits with exponential regret improvement.
problem Model selection in linear bandits is challenging due to balancing exploration and exploitation.
method ALEXP uses online learning with favorable bias-variance trade-off to emulate full-information feedback.
result ALEXP achieves an exponentially improved ( log M \log M log M ) regret dependence on the number of models M M M . Paper addresses regret minimization and inference in high-dimensional online decision-making.
problem Regret minimization and statistical inference in high-dimensional online decision-making.
method Integrates ε-greedy bandit algorithm with hard thresholding for sparse bandit parameters and debiasing method for inference.
result Achieves either O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) regret or O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) -consistent inference, with trade-off between exploration and exploitation. Market makers minimize regret by strategically setting bid and ask prices.
problem Minimizing regret in sequential market making decisions.
method Characterizes market making regret under various assumptions and distributions.
result Unveils a connection to first-price auctions and dynamic pricing.
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. New algorithms achieve optimal regret in sliding window model with limited memory.
problem Experts problem in the sliding window model with limited information.
method 2 queries, polylog(nT) memory, exponential improvement on memory.
result Achieve optimal regret of sqrt(nW)polylog(nT) with 2 queries and polylog(nT) memory.
Algorithm minimizes regret in multi-criteria bandits with constraints.
problem Optimize primary attribute while respecting secondary constraints.
method Con-LCB algorithm that guarantees logarithmic regret and feasibility identification.
result Logarithmic regret and feasibility identification with high probability.