Improved EXP3++ algorithm reduces regret in stochastic bandits.
problem Stochastic and adversarial multiarmed bandits.
method New gap estimation strategy combined with EXP3++.
result Regret reduced from to in stochastic regime.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,291 papers · 148 categories
Trend · papers per month
38 results for “EXP3++”
Study online learning with feedback graphs and switching costs, providing algorithms and optimal regret bounds.
problem Online learning with partial feedback and switching costs.
method Analysis of feedback graphs, lower bound on expected regret, new algorithms (Threshold Based EXP3, EXP3. SC).
result Order optimal algorithms for specific cases and Threshold Based EXP3 outperforms in empirical evaluations.
Near-optimal per-action regret bounds for sleeping bandits are derived.
problem Optimizing performance in sleeping bandits where arms and losses are chosen by an adversary.
method Directly minimizing per-action regret using generalized versions of EXP3, EXP3-IX, and FTRL with Tsallis entropy.
result Near-optimal bounds of order and are obtained.
UCB-RS uses RS to improve UCB for online advertising.
problem Improving recommendation in online advertising.
method UCB-RS, combining UCB with recommendation system.
result UCB-RS outperforms other reinforcement learning methods in RecoGym.
New algorithm reduces regret in Bandits with Knapsack problem.
problem Online learning with budget constraints and adversarial rewards.
method Proposes EXP3.BwK and EXP3++.BwK algorithms achieving optimal regret.
result Achieves optimal regret in adversarial setting and almost optimal in stochastic setting.
Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resourcescs.LG
A dueling bandit problem with resource constraints is solved using EXP3.
problem Maximizing rewards in dueling bandits with resource constraints.
method EXP3 algorithm considering resource consumptions.
result Achieves $ ilde{\mathcal{O}}\left({\frac{OPT^{(b)}}{B}}K^{1/3}T^{2/3}
ight)$ regret.
Upper and lower bounds derived for online learning with graph-structured feedback against adaptive adversaries.
problem Online learning with graph-structured feedback against adaptive adversaries.
method Analysis of Exp3 algorithm variants and lower bounds for specific adversary models.
result Upper bounds of and for strongly-observable and weakly-observable graphs, respectively.
New approach considers a buyer with no-regret learning to optimize seller's revenue.
problem Optimizing revenue for a seller selling to a buyer with no-regret learning.
method Analyzes different learning algorithms for the buyer and corresponding optimal auctions for the seller.
result Seller can achieve optimal revenue by setting decreasing reserves over time, surpassing truthful auctions.
New algorithm reduces sleeping bandits' regret to O(sqrt(T)).
problem Improving sleeping bandits with stochastic actions and adversarial rewards.
method Inspired by EXP3, new algorithm with regret.
result Achieves regret, improving over existing .
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.
The paper reveals that baselines significantly impact RL algorithms' convergence.
problem Understanding the true impact of baselines on policy optimization.
method Theoretical analysis of bandit and RL problems, focusing on natural policy gradient and EXP3.
result Baselines can determine algorithm convergence, contradicting traditional optimization theory.
Adapts Exp3 to adversarial bandits with delays and data.
problem Adversarial multi-armed bandits with delayed feedback.
method Tuned Exp3 variants with step-size adaptation and implicit exploration.
result Optimal regret bounds of with high probability.
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.
The paper minimizes Borda regret in dueling bandits models.
problem Minimizing Borda regret in dueling bandits models.
method Proposes explore-then-commit and EXP3-type algorithms for stochastic and adversarial settings respectively.
result Achieves nearly matching regret upper bounds of for both settings.
Unified meta-algorithm improves average performance across similar tasks in adversarial bandits.
problem Improving performance across multiple similar tasks in adversarial bandit settings.
method Unified meta-algorithm for multi-armed bandits and bandit linear optimization, tuning initialization, step-size, and entropy parameters.
result Unified meta-algorithm yields setting-specific guarantees for MAB and BLO, improving task-averaged regret.
New UCB algorithms resist contamination in bandit problems.
problem Stochastic bandit problems with ε-contaminated rewards.
method Robust mean estimators and crUCB algorithms.
result Achieves O(√KTlogT) regret for small contamination proportions.
We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir. Our main result is a characterization of regret in the directed observability model in terms of the dominating and independence numbers of the observability graph. We also show that in the undirected case, the learner …
We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularization via the \emph{Tsallis entropy}, which includes EXP3 as a special case, achieves the minim…
The paper connects discrete choice models to multi-armed bandit algorithms with sublinear regret bounds.
problem Optimizing user choices in a multi-armed bandit setting.
method Establishes connections between discrete choice models and multi-armed bandit algorithms, providing sublinear regret bounds and novel algorithms.
result Sublinear regret bounds for a family of algorithms, including the Exp3 algorithm.
New algorithms reduce rejection sampling complexity for shape-constrained distributions.
problem Generating exact samples from shape-constrained distributions efficiently.
method Sublinear query complexity algorithms for rejection sampling.
result Sublinear complexity algorithms for sampling from shape-constrained distributions.
New algorithms for online path learning with non-additive gains in various settings.
problem Online path learning with non-additive gains in ensemble structured prediction.
method Developed new online algorithms for full, semi-bandit, and full bandit settings with favorable regret guarantees.
result Efficient implementation of EXP3 algorithm for full bandit setting with arbitrary non-additive gains.
Study shows online learning algorithms incentivize low-quality content, proposing new algorithms to improve quality.
problem Online learning algorithms in content recommender systems incentivize producers to create low-quality content.
method Analyzed the game between producers and content quality, designed new learning algorithms to incentivize high effort and quality.
result New algorithms incentivize producers to invest high effort and achieve high user welfare, improving content quality.
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.
New algorithms reduce regret in adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Developed two algorithms: RealLinExp3 and RobustLinExp3.
result Achieved optimal regret bounds for the first time.
This paper shows hedging algorithms improve performance in repeated matrix games.
problem Improving multi-agent learning algorithms in repeated matrix games.
method Develops and experiments with hedging algorithms combining a top-level and a set of basic algorithms.
result Well-selected hedging algorithms outperform previous MAL algorithms on repeated matrix games.
Meta-learning improves performance across similar tasks in adversarial bandit settings.
problem Improving performance across multiple similar tasks in adversarial bandit scenarios.
method Designing meta-algorithms that combine outer learners to tune hyperparameters of inner learners for MAB and BLO.
result Meta-algorithms improve task-averaged regret for MAB and BLO, showing direct relationship with action space-dependent measures.
ABoB optimizes online configuration tuning by clustering parameters and accelerating learning.
problem Online optimization in large, dynamic parameter spaces.
method Hierarchical adversarial bandit framework.
result Significant performance gains in adversarial metric scenarios.
New method for linear bandits with unknown sparsity, improving sparse regret bounds.
problem Sparse regret bounds for unknown sparsity and adversarial action sets.
method Combines online to confidence set conversions with randomized model selection over nested confidence sets.
result First sparse regret bounds for unknown sparsity and adversarial action sets.
Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimationstat.ML
New BO method optimizes functions efficiently even with unknown hyperparameters.
problem Inaccurate estimation of Gaussian process hyperparameters degrades BO performance.
method Exploits multi-armed bandit and novel training loss function for consistent hyperparameter estimation.
result Sub-linear convergence to global optimum with unknown hyperparameters.
New sampling methods improve performance in stochastic bandits with graph feedback.
problem Stochastic multi-armed bandit problems with graph feedback.
method Information Directed Sampling (IDS) policies for graph-aware decision making.
result IDS policies provide tighter regret bounds than existing methods.
Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theoremstat.ML
Paper stabilizes bandit learning with regularization, improving inference under adaptive sampling.
problem Challenges in statistical inference with adaptive sampling.
method Refined stability condition for online algorithms, using regularized stochastic-mirror-descent-style methods.
result Derives precise regret bounds and asymptotic normality, showing necessity of regularization for valid inference.
A budget-constrained multi-armed bandit problem with multiple plays is analyzed for both stochastic and adversarial settings.
problem Optimizing decisions in a multi-armed bandit problem with a budget constraint for multiple plays.
method Upper Confidence Bound (UCB) algorithm for stochastic case and an extension of Exp3 algorithm for adversarial case.
result Achieved regret bounds for both stochastic and adversarial settings.
Optimal algorithm for both stochastic and adversarial bandits without prior knowledge.
problem Optimal algorithm for both stochastic and adversarial bandits.
method Online mirror descent with Tsallis entropy regularization and reduced-variance loss estimators.
result Achieves optimal pseudo-regret in both adversarial and stochastic bandits.
New algorithm for multiarmed bandits with variable, unbounded delays achieves similar regret bounds.
problem Variable, unbounded delays in multiarmed bandits.
method Introduces a new algorithm that skips rounds with excessively large delays and uses a doubling scheme.
result Achieves the same regret bound as Exp3 with variable, unbounded delays.
New algorithms improve exploration in unbounded reward settings.
problem Challenges in exploration with unbounded rewards in reinforcement learning.
method Proposed EXP4.P and EXP4-RL algorithms for unbounded reward settings.
result EXP4.P achieves global optimality in linear cases with one competent expert.
CMOSS algorithm reduces regret in combinatorial semi-bandits with efficient computation.
problem Efficiently solving combinatorial semi-bandit problems with minimal regret.
method CMOSS algorithm achieves optimal regret bounds with minimal computational overhead.
result CMOSS achieves optimal regret bounds with minimal computational overhead.
New algorithms for uncoordinated spectrum access with multi-user multi-armed bandits.
problem Uncoordinated spectrum access with unknown number of users and channels.
method Developed algorithms for stochastic and adversarial settings, combining Exp3.P for dynamic scenarios.
result Sub-linear regret guarantees for both stochastic and adversarial cases, even when users outnumber channels.
Optimizes SSP's header bidding strategy using Thompson Sampling.
problem Maximizing ad revenue in a competitive SSP market.
method Thompson Sampling algorithm with particle filter for correlated contexts.
result Significantly outperforms classical approaches in real datasets.