We study the Thompson sampling algorithm in an adversarial setting, specifically, for adversarial bit prediction. We characterize the bit sequences with the smallest and largest expected regret. Among sequences of length with zeros, the sequences of largest regret consist of alternating zeros and …
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,695 papers · 148 categories
Trend · papers per month
48 results for “Zero regret”
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves regret bounds, matching upper and lower bounds.
Paper finds algorithms with both low regret and high exploitation.
problem Finding algorithms with both low regret and high exploitation.
method Investigates online learning algorithms with bandit feedback.
result First affirmative answer to guaranteeing both regret and regret.
Algorithm learns from changing zero-sum games with no regret.
problem Learning in time-varying zero-sum games.
method Developed a single parameter-free algorithm with three performance measures.
result Algorithm recovers best known results for fixed games and adapts to non-stationarity.
Adam optimization algorithm can have non-zero average regret under certain conditions.
problem Non-zero average regret in Adam optimization algorithm.
method Used a three-periodic sequence of linear functions on [-1,1] with slopes c, -1, -1, and analyzed Adam variants.
result Adam optimization algorithm can have non-zero average regret under certain conditions.
In this paper, we formalise order-robust optimisation as an instance of online learning minimising simple regret, and propose Vroom, a zero'th order optimisation algorithm capable of achieving vanishing regret in non-stationary environments, while recovering favorable rates under stochastic reward-generating processes.…
A new multi-armed bandit framework with credal sets for uncertain outcomes.
problem Optimizing decisions under uncertainty with unknown outcomes.
method Introduces a novel multi-armed bandit framework with credal sets and defines regret as lower prevision.
result Upper bounds on regret for certain hypothesis classes and lower bounds for special cases.
Paper develops efficient algorithms for zero-sum Markov games with general function classes.
problem Challenging settings in zero-sum Markov games with parameterized value functions or models.
method Developed new model-free and model-based algorithms for decoupled and coordinated settings.
result Improved sample complexity and regret bounds for various settings.
Optimizing Regretecon.EM
The paper optimizes regret using covariance between costs and decisions.
problem Optimizing expected regret in decision-making problems.
method Developed derivative theory of covariance regret functional, derived Gâteaux derivative, and extended to constrained optimization.
result Gradient of covariance regret is the cost covariance matrix, with implications for portfolio optimization.
New algorithm for multi-player bandits with collision-dependent rewards.
problem Stochastic multi-player multi-armed bandits with collision-dependent reward distributions.
method Error-Correction Collision Communication (EC3) algorithm.
result EC3 algorithm achieves optimal regret approaching centralized MP-MAB regret.
This paper improves Thompson Sampling for complex decision-making problems.
problem Learning in infinite-horizon discounted decision processes with unknown parameters.
method Developed a general canonical probability space and new metrics for analyzing adaptive learning algorithms.
result Thompson Sampling achieves complete learning in complex decision-making problems.
The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
Study analyzes symmetric two-armed Bernoulli bandit problem with zero mean gap.
problem Analyzing symmetric two-armed Bernoulli bandit problem with zero mean gap.
method Associated with a solution of a linear heat equation, compute leading order terms of minmax optimal regret and pseudoregret.
result Explicitly compute leading order terms in three scaling regimes for the gap.
We study the problem of repeated play in a zero-sum game in which the payoff matrix may change, in a possibly adversarial fashion, on each round; we call these Online Matrix Games. Finding the Nash Equilibrium (NE) of a two player zero-sum game is core to many problems in statistics, optimization, and economics, and fo…
New algorithms achieve logarithmic regret in KL-regularized Markov games.
problem Improving sample efficiency in game-theoretic settings with KL regularization.
method Developed OMG and SOMG algorithms for matrix and Markov games, using best response sampling and superoptimistic bonuses.
result Logarithmic regret in that scales inversely with KL regularization strength .
qEUBO optimizes decision-making with noisy feedback.
problem Optimizing decision-making with noisy preference feedback.
method Introduces qEUBO as a novel acquisition function for preferential Bayesian optimization.
result qEUBO is one-step Bayes optimal and enjoys an approximation guarantee under noise.
Study optimizes zero-order strongly convex function minimization with higher order smoothness.
problem Optimizing a strongly convex function with noisy evaluations.
method Randomized approximation of projected gradient descent with smoothing kernel.
result Upper bounds and minimax lower bounds for the algorithm, showing near-optimality.
Improved regret bounds for bandits with fixed expert advice using information theory.
problem Optimizing regret in bandit problems with fixed expert distributions.
method Information-theoretic analysis and KL-divergence measures.
result First regret bounds for EXP4 that can get arbitrarily close to zero under certain conditions.
Influence maximization, adaptive routing, and dynamic spectrum allocation all require choosing the right action from a large set of alternatives. Thanks to the advances in combinatorial optimization, these and many similar problems can be efficiently solved given an environment with known stochasticity. In this paper, …
A new metric, Weighted Regret, unifies FDR and power evaluation in online multiple testing.
problem The asymmetric costs of false positives and false negatives in automated pipelines.
method Introducing Weighted Regret and Decoupled-OMT (DOMT) to unify FDR and power evaluation.
result DOMT achieves an order-optimal sublinear mitigation of threshold depletion in bursty environments.
Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we…
New DP algorithms achieve near-optimal regret bounds for online learning problems.
problem Online learning problems with zero-loss solutions and differential privacy constraints.
method Developed new Differentially Private algorithms with near-optimal regret bounds.
result Achieved near-optimal regret bounds for various online prediction and convex optimization problems.
We consider the multi-armed bandit setting with a twist. Rather than having just one decision maker deciding which arm to pull in each round, we have different decision makers (agents). In the simple stochastic setting, we show that a "free-riding" agent observing another "self-reliant" agent can achieve just $O(1)…
Gaptron algorithm reduces mistakes in online multiclass classification.
problem Online multiclass classification with limited information.
method Randomized first-order algorithm exploiting the gap between zero-one loss and surrogate losses.
result First linear time algorithm with expected regret.
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…
Study lenient regret and good-action identification in Gaussian process bandits.
problem Optimizing function values above a certain threshold in Gaussian process bandits.
method Study lenient regret notions and introduce algorithms for finding good actions.
result Upper and lower bounds on lenient regret for GP-UCB and elimination algorithms.
Two algorithms improve online reinforcement learning in adversarial linear MDPs with bandit feedback.
problem Online reinforcement learning in linear MDPs with adversarial losses and bandit feedback.
method Two algorithms: one computationally inefficient with $\widetilde{\mathcal{O}}\left(\sqrt{K}
ight)$ regret, and one computationally efficient with $\widetilde{\mathcal{O}}\left(K^{\frac{3}{4}}
ight)$ regret.
result Achieved improved regret performance compared to existing approaches.
We study the non-stationary stochastic multiarmed bandit (MAB) problem and propose two generic algorithms, namely, the limited memory deterministic sequencing of exploration and exploitation (LM-DSEE) and the Sliding-Window Upper Confidence Bound# (SW-UCB#). We rigorously analyze these algorithms in abruptly-changing a…
New algorithm for countable bandits with optimal regret.
problem Stochastic bandit problem with countably many arms.
method Fully adaptive online learning algorithm with O(log n) expected cumulative regret.
result Achieves optimal regret of O(log n) after any number of plays n.
Algorithm optimizes spectrum access for dynamic multi-user environments.
problem Optimizing spectrum access in uncoordinated multi-user environments with potential collisions.
method Stochastic multi-user bandit framework with estimation and allocation phases.
result Order-optimal system-wide regret of for dynamic and static cases.
N-discount optimality was introduced as a hierarchical form of policy- and value-function optimality, with Blackwell optimality lying at the top level of the hierarchy Veinott (1969); Blackwell (1962). We formalize notions of myopic discount factors, value functions and policies in terms of Blackwell optimality in MDPs…
Optimal algorithm for two-player zero-sum games with linear parameterization.
problem Finding Nash Equilibrium in two-player zero-sum Markov games with linear transition.
method Nash-UCRL algorithm, Coarse Correlated Equilibrium, Optimism-in-Face-of-Uncertainty.
result Proves regret bound, matching lower bound up to logarithmic factors.
We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider two feedback models: a model in which the players can observe whether a collision has occurred an…
Bayesian methods suffer from the problem of how to specify prior beliefs. One interesting idea is to consider worst-case priors. This requires solving a stochastic zero-sum game. In this paper, we extend well-known results from bandit theory in order to discover minimax-Bayes policies and discuss when they are practica…
This paper analyses the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) pro…
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcs.LG
New algorithms minimize regret in SSP with optimal sparse updates.
problem Minimizing regret in Stochastic Shortest Path models.
method Implicit finite-horizon approximation for analysis, model-free and model-based algorithms developed.
result Minimax optimal regret for both model-free and model-based algorithms.
This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al, 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, Srinivas et al proved that t…
New betting strategy reduces regret to ln(ln n) with protection against adversarial data.
problem Tackles the problem of minimizing regret in betting against adversarial and stochastic data.
method Combines insights from Robbins and Cover, using a mixture strategy.
result Exhibits a regret of O(ln(ln n)) on almost all paths, with O(log n) regret on the complement.
Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect informationcs.LG
Counterfactual regret minimization (CFR) is the most popular algorithm on solving two-player zero-sum extensive games with imperfect information and achieves state-of-the-art performance in practice. However, the performance of CFR is not fully understood, since empirical results on the regret are much better than the …
Optimal online data collection for semiparametric inference reduces regret.
problem Sequential data collection decisions for efficient estimation under budget constraints.
method Online Moment Selection framework; Explore-then-Commit and Explore-then-Greedy policies.
result Online data collection policies achieve zero regret relative to an oracle policy.
In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptim…
We address the issue of limit cycling behavior in training Generative Adversarial Networks and propose the use of Optimistic Mirror Decent (OMD) for training Wasserstein GANs. Recent theoretical results have shown that optimistic mirror decent (OMD) can enjoy faster regret rates in the context of zero-sum games. WGANs …
Enhanced -consistency bounds derived under relaxed conditions.
problem Quantifying the relationship between zero-one estimation error and surrogate loss estimation error.
method Relaxing the condition on the surrogate loss conditional regret and presenting a general framework for establishing enhanced -consistency bounds.
result Derivation of more favorable -consistency bounds in various scenarios.
New algorithm robust to outliers in Bayesian Optimization.
problem Vulnerability of Bayesian Optimization to extreme outliers.
method Introduces a new adversary with a frequency-bounded corruption budget and derives RCGP-UCB algorithm.
result Achieves sublinear regret in the presence of up to and corruptions with possibly infinite magnitude.
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.
Paper achieves logarithmic regret for online Kalman filter learning.
problem Predicting observations from an unknown, partially observed linear system with stochastic noise.
method Online least-squares algorithm exploiting the approximate linearity of Kalman filter predictions.
result Achieves regret of order poly(log(N)) with high probability.
RLCFR improves CFR's generalization in imperfect information games.
problem Improving CFR's performance in large-scale, imperfect information games.
method RLCFR integrates CFR with deep reinforcement learning to update strategies dynamically.
result RLCFR significantly enhances CFR's generalization ability in various games.
New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves Bayesian regret for stochastic multi-armed bandits.