We study the problem of regret minimization for distributed bandits learning, in which agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the…
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,742 papers · 148 categories
Trend · papers per month
48 results for “near-optimal regrets”
Paper tackles non-stationary kernelized bandits with near-optimal algorithm.
problem Minimizing regret in a time-varying reward function.
method Near-optimal algorithm with a novel restarting phased elimination with random permutation (R-PERP).
result Regret upper bound matches the lower bound, making the algorithm near-optimal.
Improved algorithm for adaptive dueling bandits with near-optimal regret bound.
problem Non-stationary dueling bandits with unknown number of preference changes.
method Elimination-based rescheduling algorithm for adaptive dynamic regret.
result Near-optimal dynamic regret bound.
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.
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.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
GN algorithm solves batched bandit for nondegenerate functions near-optimally.
problem Batched bandit learning for nondegenerate functions.
method Introduces Geometric Narrowing (GN) algorithm with a regret bound and batches.
result GN achieves near optimal regret with minimal number of batches.
New algorithms reduce reinforcement learning regret in factored MDPs.
problem Optimizing reinforcement learning in non-episodic factored MDPs.
method Proposed two near-optimal and oracle-efficient algorithms for FMDPs.
result Oracle-efficient algorithms achieve near-optimal regret bounds of .
New algorithm reduces regret by focusing on near-optimal actions.
problem Regret minimization in multi-armed bandits leads to over-exploitation.
method Proposes a lenient regret criterion and a new algorithm, ε-TS.
result ε-TS achieves asymptotic optimality in lenient regret.
Balances the regret of different algorithms in bandit and RL problems.
problem Model selection in bandit and reinforcement learning.
method Estimates and balances the empirical regrets of algorithms.
result Achieves near-optimal regret compared to the optimal base algorithm.
New method achieves near-optimal regret without simulator.
problem Adversarial linear contextual bandits with unknown loss vectors.
method Near-optimally reduces regret to sqrt(T) without simulator.
result Achieves regret of sqrt(T) without simulator, improving existing methods.
Near-optimal algorithms for predicting across multiple loss functions efficiently.
problem Predicting optimally across various loss functions simultaneously.
method Developed near-optimal online and offline learning algorithms for omniprediction.
result Achieved near-optimal complexity for both online and offline settings.
Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer regret on some MDP, where is the elapsed time and and are the cardinalities of the state and action spaces. This implies time to guarantee a near-optimal policy. In many settings…
New method reduces multi-armed bandit regret to near-optimal levels.
problem Improving regret bounds for KL-regularized multi-armed bandits.
method Sharp analysis of KL-UCB with peeling argument.
result First high-probability regret bound with linear dependence on K.
New algorithms minimize risk in MNL bandits, achieving near-optimal performance.
problem Minimizing risk in multi-armed bandit problems.
method Designing algorithms for various risk criteria (e.g., CVaR, Sharpe ratio, entropy risk).
result Near-optimal regret for the designed algorithms.
New algorithms reduce dynamic regret in non-stationary RL environments.
problem Optimizing policies in environments that change over time.
method POWER and POWER++ algorithms for policy optimization with dynamic regret analysis.
result POWER++ improves dynamic regret by actively adapting to non-stationarity.
New online conformal prediction methods minimize strongly adaptive regret and achieve near-optimal coverage.
problem Uncertainty quantification in online settings with changing data distributions.
method Developed new online conformal prediction methods that minimize strongly adaptive regret.
result Achieve near-optimal strongly adaptive regret and approximately valid coverage.
Improved online algorithm for convex losses with near-optimal swap regret.
problem Minimizing swap regret for convex losses.
method Randomized online algorithm using multi-scale binning.
result Near-optimal expected swap regret.
New algorithms combat adversarial attacks in stochastic linear bandits.
problem Adversarial attacks on stochastic linear bandit rewards.
method Two variants of Robust Phased Elimination algorithms, one knowing and one not.
result Near-optimal regret in non-corrupted case and additive terms dependent on .
We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret o…
A collaborative algorithm reduces regret in federated linear contextual bandits.
problem Optimizing decision-making in federated learning with heterogeneous data.
method Fed-PE algorithm, leveraging geometric structure of rewards, multi-client G-optimal design.
result Achieves near-optimal regrets with logarithmic communication costs.
New algorithms minimize dynamic regret for strongly convex losses.
problem Minimizing dynamic regret for strongly convex losses.
method Developed Strongly Adaptive algorithms exploiting KKT conditions.
result Achieved near optimal dynamic regret of .
A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regretcs.LG
A new model-free algorithm achieves near-optimal regret for infinite-horizon MDPs.
problem Model-free reinforcement learning for infinite-horizon average-reward MDPs.
method Exploration Enhanced Q-learning (EE-QL) for weakly communicating MDPs.
result Achieves regret bound for general weakly communicating MDPs.
Study optimal control in unknown nonlinear systems with near-optimal regret bound.
problem Sequential control in unknown, nonlinear dynamical systems.
method LC^3 algorithm, based on information theory.
result Near-optimal regret bound for episodic settings.
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 calls to an offline regression oracle.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
Algorithm reduces regret in safe Bayesian optimization with monotonicity constraints.
problem Sequentially maximize unknown function with safety constraints.
method Sequential algorithms using Gaussian processes with safety constraints modeled as monotonicity.
result Sublinear regret achieved for expanding safe region and finding optimal .
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 offline oracle calls.
We investigate the use of bootstrapping in the bandit setting. We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and establish a near-linear lower bound on the regret incurred by it under the bandit model with Bernoulli rewards. We show that NPB with an approp…
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. In this paper, we …
Improved privacy in RL with near-optimal regret bounds.
problem Privacy-preserving reinforcement learning in personalized decision-making systems.
method Differentially private algorithm based on LSVI-UCB++ with privacy-preserving techniques.
result Achieved a near-optimal regret bound of O(d * sqrt(H^3 * K) + H^(15/4) * d^(7/6) * K^(1/2) / ε).
LinMED is a new linear bandit algorithm with near-optimal regret bound.
problem Optimizing decision-making in linear bandit problems with sub-Gaussian distributions.
method LinMED is a randomized linear bandit algorithm with closed-form arm sampling probabilities.
result LinMED achieves a near-optimal regret bound of up to logarithmic factors.
This paper tackles near-optimal adversarial RL with switching costs, providing algorithms and matching lower bounds.
problem Adversarial RL with switching costs, where loss distribution can be non-stationary or adversarial.
method Developed novel switching-reduced algorithms with matching lower bounds for known and unknown transition functions.
result Achieved near-optimal performance in adversarial RL with switching costs, matching theoretical lower bounds.
Algorithm minimizes regret in predictive models influenced by their own predictions.
problem Finding near-optimal models under performativity with unknown shifts.
method Developed an algorithm that uses performative feedback to achieve low regret, scaling only with distribution shift complexity.
result Achieved regret bounds scaling with distribution shift complexity, not reward function complexity.
We provide a simple and efficient algorithm for adversarial -action -outcome non-degenerate locally observable partial monitoring game for which the -round minimax regret is bounded by , matching the best known information-theoretic upper bound. The same algorithm also achieves…
The paper tackles cooperative RL with function approximation, achieving near-optimal learning with limited communication.
problem Cooperative multi-agent reinforcement learning with function approximation.
method Careful message-passing and cooperative value iteration.
result Achieving near-optimal no-regret learning with limited communication in cooperative multi-agent settings.
FTPL with Fréchet perturbation achieves near optimal regret bounds for m-set semi-bandit problems.
problem Optimizing regret bounds for m-set semi-bandit problems in adversarial and stochastic settings.
method Follow-the-Perturbed-Leader (FTPL) with Fréchet perturbation.
result Achieves near optimal regret bounds of in adversarial setting and logarithmic regret in stochastic setting.
We consider a variation on the problem of prediction with expert advice, where new forecasters that were unknown until then may appear at each round. As often in prediction with expert advice, designing an algorithm that achieves near-optimal regret guarantees is straightforward, using aggregation of experts. However, …
We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual…
Two non-communicating players minimize regret in a multi-armed bandit game.
problem Optimal regret in non-communicating multi-armed bandit players.
method Proposed a strategy with no collisions, achieving near-optimal regret.
result Near-optimal regret of with very high probability.
New algorithm for collaborative bandit learning reduces sample complexity and regret.
problem Optimal arm identification in a multi-agent bandit model with communication.
method Phased elimination with data-dependent sampling schemes.
result Near-optimal algorithm for pure exploration in collaborative bandit learning.
Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningstat.ML
New RL algorithms reduce costs for single-agent and federated learning.
problem Minimizing costs in RL and federated RL settings.
method Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost algorithms.
result First algorithms to achieve low burn-in and logarithmic switching costs.
New algorithms achieve near-optimal cumulative loss in nonparametric online learning and games.
problem Fast rates of convergence in nonparametric online regression and classification.
method Randomized proper learning algorithms, hierarchical aggregation, multi-scale extension, stability proof.
result Achieved near-optimal cumulative loss bounds for real-valued and binary games.
New algorithm reduces switching costs in RL beyond linear MDPs.
problem Costly policy switching in reinforcement learning.
method ELEANOR-LowSwitching algorithm for linear Bellman-complete MDPs.
result Achieves near-optimal regret with logarithmic switching cost.
New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
Study collaborative learning among multi-agents in multi-armed bandits.
problem Minimizing group cumulative regret in a heterogeneous multi-agent setting.
method Developed decentralized algorithms for collaboration between agents learning stochastic multi-armed bandits.
result Proved near-optimal behavior of proposed algorithms for group regret.
StepMix algorithm ensures safe exploration in reinforcement learning with near-optimal performance.
problem Conservative exploration in reinforcement learning under episode-wise constraints.
method StepMix algorithm balances exploitation and exploration while ensuring episode-wise conservative constraint.
result StepMix achieves near-optimal regret order as in the constraint-free setting.
Efficient algorithm for near-optimal online learning with generalized linear functions.
problem Exponential gap between statistically optimal regret and efficient regret for some function classes.
method Computational efficient algorithm for realizable K-wise linear classification and over-parameterized polynomial featurization.
result First algorithm with log(T/σ) regret for realizable K-wise linear classification.