We consider a collaborative online learning paradigm, wherein a group of agents connected through a social network are engaged in playing a stochastic multi-armed bandit game. Each time an agent takes an action, the corresponding reward is instantaneously observed by the agent, as well as its neighbours in the social n…
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 “Network Regret”
Algorithm optimizes cascaded functions with known structure.
problem Optimizing a function network with known structure.
method GPN-UCB algorithm with upper confidence bounds and theoretical regret bounds.
result Near-optimal cumulative and simple regret bounds.
New algorithms use neural networks to minimize regret in contextual bandits.
problem Minimizing regret in sequential decisions with side information.
method Proposes NN-UCB and NTK-UCB algorithms using neural networks.
result Proves sublinear regret bounds for contextual bandits.
Flooding with Absorption: An Efficient Protocol for Heterogeneous Bandits over Complex Networkscs.LG
New protocol reduces communication costs for heterogeneous bandits over complex networks.
problem Minimizing group regret in a multi-agent, heterogeneous bandit setting over complex networks.
method Flooding with Absorption (FwA) protocol for heterogeneous bandits over complex networks.
result FwA protocol significantly reduces communication costs compared to flooding while maintaining similar regret performance.
New algorithm minimizes regret in multi-armed bandits with network interference.
problem Minimizing regret in online experiments with network interference.
method Sparse network interference model, discrete Fourier analysis, linear regression-based algorithms.
result Provable low regret algorithms for sparse interference networks.
This work improves online regression and contextual bandits using neural networks.
problem Improving online regression and contextual bandits using neural networks.
method Investigates neural networks for online regression, showing regret for almost convex losses and KL loss.
result Shows regret for NeuCB, outperforming existing algorithms.
Bayesian algorithms minimize cumulative regret in decentralized multi-agent bandits.
problem Minimizing cumulative regret in a decentralized multi-agent multi-armed bandit problem.
method Proposed decentralized Bayesian multi-armed bandit framework, including Thompson Sampling and Bayes-UCB algorithms.
result Regret scales logarithmically with constants matching those of an optimal centralized agent.
We study an asynchronous online learning setting with a network of agents. At each time step, some of the agents are activated, requested to make a prediction, and pay the corresponding loss. The loss function is then revealed to these agents and also to their neighbors in the network. Our results characterize how much…
New algorithms reduce dueling bandits' regret with neural networks and efficient exploration.
problem Optimizing dueling bandits with neural networks for better performance.
method Combines shallow exploration strategies with neural networks for utility approximation, using iterative self-improvement and spectral analysis to reduce network width.
result Achieves sublinear regret of .
Adaptive gradient methods have become recently very popular, in particular as they have been shown to be useful in the training of deep neural networks. In this paper we have analyzed RMSProp, originally proposed for the training of deep neural networks, in the context of online convex optimization and show -…
New algorithm reduces regret in asynchronous multiplayer bandits to constant or logarithmic levels.
problem Asynchronous multiplayer bandits in cognitive radio networks.
method Cautious Greedy algorithm with minimax regret.
result Cautious Greedy yields constant instance-dependent regret under certain conditions.
We study a decentralized cooperative stochastic multi-armed bandit problem with arms on a network of agents. In our model, the reward distribution of each arm is the same for each agent and rewards are drawn independently across agents and time steps. In each round, each agent chooses an arm to play and subsequ…
Algorithm learns interference network and optimizes treatment allocation for unknown network effects.
problem Adaptive experimentation under unknown network interference.
method Thompson sampling algorithm with Gibbs sampler for joint learning of interference network and treatment allocation.
result Proves a Bayesian regret bound and achieves sublinear regret in real-world applications.
New algorithm reduces regret in multi-agent bandits over undirected graphs.
problem Minimize regret in a multi-agent bandit setting with malicious agents.
method Proposed a new algorithm for undirected graphs, considering the number of malicious neighbors.
result The new algorithm achieves nearly linear regret improvement over existing methods.
We introduce efficient algorithms which achieve nearly optimal regrets for the problem of stochastic online shortest path routing with end-to-end feedback. The setting is a natural application of the combinatorial stochastic bandits problem, a special case of the linear stochastic bandits problem. We show how the diffi…
ESCHER avoids importance sampling to estimate regret in large games.
problem Estimating Nash equilibria in large games with high variance.
method Computes a history value function to estimate regret without importance sampling.
result ESCHER reduces regret estimation variance significantly compared to existing methods.
Neural Thompson Sampling uses deep neural networks for contextual bandit problems.
problem Solving contextual multi-armed bandit problems.
method Adapts deep neural networks for exploration and exploitation in a novel posterior distribution.
result Guaranteed cumulative regret of for bounded reward functions.
The paper tackles adaptive targeting in networks with interference effects.
problem Adaptive targeting under network interference in a bandit setting.
method Linear model in a sparse regime, analyzing different levels of knowledge of the interference structure.
result Unified view of how knowledge of the interference structure affects online learning efficiency.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
Permutation-equivariant neural networks improve auction mechanisms by reducing regret and sample complexity.
problem Designing optimal auction mechanisms that balance revenue and bidders' regret.
method Introduced permutation-equivariant neural networks to auction mechanisms.
result Permutation-equivariant neural networks decrease expected ex-post regret and improve model generalizability.
New algorithm reduces age of information in wireless networks with unknown channel reliability.
problem Learning optimal source-channel pairs to minimize age of information in wireless networks.
method Introduces AoI regret, novel learning algorithm with bounded AoI regret.
result Developed a learning algorithm with AoI regret, improving upon .
A decentralized algorithm minimizes cumulative regret in stochastic linear bandits with safety constraints.
problem Efficiently solving a linear bandit-optimization problem over a network of agents with safety constraints.
method DLUCB: a fully decentralized algorithm that minimizes cumulative regret through UCB strategy and consensus procedure.
result Near-optimal regret performance of with communication rate.
Distributed Thompson sampling improves regret convergence in constrained communication networks.
problem Maximizing a black-box function with multi-agent Bayesian optimization under communication constraints.
method Distributed Thompson sampling using Gaussian processes, with theoretical bounds on regret convergence.
result Theoretical bounds on Bayesian average and simple regret depend on communication graph structure and are applicable in constrained networks.
New algorithm reduces regret in collaborative multi-agent bandit problems.
problem Optimizing decisions in a network of agents with communication delays.
method Follow-the-Regularized-Leader (FTRL) algorithm with suitable regularizers and communication protocols.
result Upper bound on individual regret matches lower bound up to a constant factor.
Study on deep neural networks for reward modeling with pairwise comparison data.
problem Reward modeling with deep neural networks in non-parametric settings.
method Established a non-asymptotic regret bound for deep reward estimators, introduced a margin-type condition.
result Improved regret bound for deep reward estimators, highlighting the importance of clear human beliefs.
A new algorithm for social network recommendations using side-observations.
problem Designing recommendation algorithms for users influenced by their social network.
method Contextual bandits with side-observations modeled by a social network graph.
result The proposed algorithm achieves asymptotically optimal regret, matching the lower-bound as .
Coop-FTPL algorithm minimizes network regret in semi-bandit settings.
problem Online combinatorial optimization with semi-bandit feedback on a network of agents.
method Cooperative Follow The Perturbed Leader (Coop-FTPL) algorithm with new loss estimation procedure.
result Expected regret of Coop-FTPL is of order Q mkT log(k)(kα1 /Q + m), with a state-of-the-art computational complexity of T^3/2.
This thesis analyzes MACL systems with low-regret learning algorithms for sequential decision making.
problem Designing efficient learning algorithms for multi-agent cooperative systems to minimize regret.
method Analyzes and develops algorithms for cooperative multi-agent multi-armed bandit problems and online convex optimization in distributed settings.
result Presented regret lower bounds and efficient algorithms for achieving these bounds, providing guidance on communication protocols.
Designs adaptive controller for networked control systems with wireless data transmission.
problem Adaptive control in networked systems with unreliable wireless channels.
method Upper Confidence Bounds for Networked Control Systems (UCB-NCS) learning rule.
result Non-asymptotic performance guarantees with a regret bound of O(C√T).
The paper identifies network bottlenecks using minimax paths in stochastic networks.
problem Identifying bottlenecks in networks with stochastic weights.
method Modeling as combinatorial semi-bandit problem, applying combinatorial Thompson Sampling, and approximating the original objective due to computational intractability.
result Established an upper bound on Bayesian regret and evaluated Thompson Sampling performance on real-world networks.
New algorithms reduce regret in neural logistic bandits.
problem Learning unknown reward functions in neural networks.
method Introduced a Bernstein-type inequality for self-normalized vector-valued martingales.
result Regret bounds improved to and .
A new exploration strategy for contextual bandits reduces regret and is computationally efficient.
problem Improving exploration in contextual bandits to reduce regret.
method Feature perturbation, injecting randomness directly into feature inputs.
result Achieves worst-case regret bound, surpassing existing methods.
Improved algorithm reduces regret in NRM with unknown demand.
problem Optimizing prices for products with limited resources under unknown demand.
method Primal-dual optimization with demand balancing.
result Improved regret bound of .
Improved Politex algorithm reduces regret bound to O(√T) with experience replay.
problem Learning in infinite-horizon MDPs with function approximation.
method Sharpened regret analysis of Politex algorithm, experience replay implementation.
result First high-probability O(√T) regret bound for computationally efficient algorithm.
New algorithm tackles non-linear utility in MNL bandits with regret.
problem Sequential assortment selection with intricate user-item interactions.
method Upper Confidence Bound principle for non-linear parametric utility functions, including neural networks.
result Achieves regret bound for neural network-based utilities.
Study cooperative bandit learning with imperfect communication, achieving near-optimal performance.
problem Real-world distributed decision-making with imperfect communication.
method Proposed decentralized algorithms for three communication scenarios: stochastic networks, random delays, and adversarially corrupted rewards.
result Achieved competitive performance and near-optimal guarantees on group regret.
Optimal vehicle repositioning policy found for shared mobility services.
problem Matching fixed supply with spatial customer demand under uncertain and correlated demand.
method Base-stock repositioning policy, asymptotic optimality, regret analysis, adaptive repositioning algorithm.
result Surrogate Optimization and Adaptive Repositioning algorithm achieves optimal regret of .
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…
Paper improves CMAB regret bounds by reducing batch-size dependency.
problem Reducing batch-size dependency in combinatorial semi-bandits.
method Developed BCUCB-T and SESCB algorithms with new TPVM conditions.
result Significantly improved regret bounds for various applications.
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 .
Optimal learning rate schedules for SGD in changing data distributions.
problem Minimizing regret in online learning with changing data distributions.
method Characterized optimal schedules for linear regression, proposed schedules for general convex and non-convex losses, and defined a notion of regret for non-convex losses.
result Upper and lower bounds for regret with constants for convex losses, and an upper bound on total expected regret for non-convex losses.
Combinatorial Neural Banditsstat.ML
New algorithms for neural bandits learn from context and arm features.
problem Learning from context and arm features in combinatorial bandit problems.
method Proposed algorithms CN-UCB and CN-TS using deep neural networks.
result Achieved regret guarantees for the first time in combinatorial neural bandits.
Study how communication and feedback graphs affect learning outcomes.
problem Understanding the impact of feedback graphs on cooperative online learning.
method Analyzed network regret in terms of the independence number of the strong product of communication and feedback graphs.
result Proved bounds for network regret and demonstrated the non-improvable nature of positive results in pathological cases.
Agents collaborate to minimize regret while keeping costs under a threshold.
problem Collaborative multi-agent stochastic linear bandits with cost constraints.
method Safe distributed upper confidence bound algorithm (MA-OPLB) with accelerated consensus.
result Regret bound of order $ \mathcal{O}\left(\frac{d}{τ-c_0}\frac{\log(NT)^2}{\sqrt{N}}\sqrt{\frac{T}{\log(1/|λ_2|)}}
ight)$.
We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multi-armed bandit problem. We derive regret minimization algorithms that guarantee for each agent an individual expected regret of $\widetilde{O}\left(\sqrt{\left(…
Improved neural active learning algorithms reduce regret and improve performance.
problem Improving performance and reducing regret in neural active learning for non-parametric streaming data.
method Introducing two new regret metrics and leveraging NNs for both exploitation and exploration. The algorithm uses tailored query decision-makers and full feedback.
result Achieved an instance-dependent regret upper bound improving by a multiplicative factor of and removing the curse of dimensionality.
A novel approach tackles sparse linear bandits with reduced communication costs and minimal cumulative regret.
problem Sparse linear bandits with high-dimensional feature vectors and limited relevant features.
method Cooperative Thresholded Lasso using Lasso and ridge regression for dimension reduction and aggregation.
result Regret bound of with high probability.