We study online learning when partial feedback information is provided following every action of the learning process, and the learner incurs switching costs for changing his actions. In this setting, the feedback information system can be represented by a graph, and previous works studied the expected regret of the le…
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.
168,694 papers · 148 categories
Trend · papers per month
48 results for “Exp3 algorithm”
We present a new strategy for gap estimation in randomized algorithms for multiarmed bandits and combine it with the EXP3++ algorithm of Seldin and Slivkins (2014). In the stochastic regime the strategy reduces dependence of regret on a time horizon from to and eliminates an additive factor of o…
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.
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.
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.
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.
Motivated by applications of bandit algorithms in education, we consider a stochastic multi-armed bandit problem with -contaminated rewards. We allow an adversary to give arbitrary unbounded contaminated rewards with full knowledge of the past and future. We impose the constraint that for each time the…
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.
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.
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.
This paper investigates the adversarial Bandits with Knapsack (BwK) online learning problem, where a player repeatedly chooses to perform an action, pays the corresponding cost, and receives a reward associated with the action. The player is constrained by the maximum budget that can be spent to perform actions, an…
We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisio…
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 study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and…
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…
In this paper, the method UCB-RS, which resorts to recommendation system (RS) for enhancing the upper-confidence bound algorithm UCB, is presented. The proposed method is used for dealing with non-stationary and large-state spaces multi-armed bandit problems. The proposed method has been targeted to the problem of the …
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.
Playing repeated matrix games (RMG) while maximizing the cumulative returns is a basic method to evaluate multi-agent learning (MAL) algorithms. Previous work has shown that , , or algorithms have good behaviours on average in RMG. Besides, hedging algorithms have been shown to be effective on predi…
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.
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.
We consider an adversarial variant of the classic -armed linear contextual bandit problem where the sequence of loss functions associated with each arm are allowed to change without restriction over time. Under the assumption that the -dimensional contexts are generated i.i.d.~at random from a known distributions…
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.
We derive upper and lower bounds for the policy regret of -round online learning problems with graph-structured feedback, where the adversary is nonoblivious but assumed to have a bounded memory. We obtain upper bounds of and for strongly-observable and weakly-observab…
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.
We derive an algorithm that achieves the optimal (within constants) pseudo-regret in both adversarial and stochastic multi-armed bandits without prior knowledge of the regime and time horizon. The algorithm is based on online mirror descent (OMD) with Tsallis entropy regularization with power and reduced-varian…
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.
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.
We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly out of possible arms have to be played (with ). In addition to observing the individual rewards for each arm played, the player also lea…
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.
We investigate multiarmed bandits with delayed feedback, where the delays need neither be identical nor bounded. We first prove that "delayed" Exp3 achieves the regret bound conjectured by Cesa-Bianchi et al. [2019] in the case of variable, but bounded delays. Here, is the number of actio…
A multi-user multi-armed bandit (MAB) framework is used to develop algorithms for uncoordinated spectrum access. The number of users is assumed to be unknown to each user. A stochastic setting is first considered, where the rewards on a channel are the same for each user. In contrast to prior work, it is assumed that t…
We consider stochastic multi-armed bandit problems with graph feedback, where the decision maker is allowed to observe the neighboring actions of the chosen action. We allow the graph structure to vary with time and consider both deterministic and Erdős-Rényi random graph models. For such a graph feedback model, we fir…
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.
Over the last decade, digital media (web or app publishers) generalized the use of real time ad auctions to sell their ad spaces. Multiple auction platforms, also called Supply-Side Platforms (SSP), were created. Because of this multiplicity, publishers started to create competition between SSPs. In this setting, there…
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.
Examines algorithmic modeling across three cultures.
problem Tackles algorithmic modeling in different cultural contexts.
method Uses parametric regressions, interpretable algorithms, and complex algorithms.
result Extension of Leo Breiman's thesis to include cultural differences.
Meta-algorithm selection aims to choose the best algorithm selector for a given problem instance.
problem Selecting the best algorithm selector for a specific problem instance.
method Apply algorithm selection to the selection of other algorithms (meta-algorithm selection).
result Meta-algorithm selection can be beneficial in some cases but faces challenges in solving the meta-level problem.
Proposes CLRS benchmark to evaluate algorithmic reasoning.
problem Difficulty in transferring results across publications due to targeted algorithmic data.
method Develops a comprehensive benchmark covering various algorithmic tasks.
result Demonstrates performance of algorithmic reasoning baselines on the CLRS benchmark.
Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learningcs.LG
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known rando…
The exchange algorithm is studied for its convergence and asymptotic variance.
problem Theoretical limitations of the exchange algorithm in sampling from doubly-intractable distributions.
method Theoretical analysis of the exchange algorithm's convergence speed and asymptotic variance.
result The exchange algorithm converges at a geometric rate and satisfies a Central Limit Theorem.
Bayesian networks (BN) are used in a big range of applications but they have one issue concerning parameter learning. In real application, training data are always incomplete or some nodes are hidden. To deal with this problem many learning parameter algorithms are suggested foreground EM, Gibbs sampling and RBE algori…
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
This review article surveys data augmentation MCMC algorithms.
problem Sampling from intractable probability distributions.
method Comprehensive study of DA MCMC algorithms, their convergence properties, and acceleration strategies.
result Synthesizes recent developments and provides insights for researchers.
The Bayesian Learning Rulestat.ML
Bayesian learning rule unifies and generalizes various machine learning algorithms.
problem Machine learning algorithms are diverse and not always understood.
method Bayesian principles and natural gradients are used to derive algorithms.
result Derives a wide range of algorithms including classical and modern ones.