Papers

Field

Top tools here

Open problems in Linear bandits

Handling non-stationary environments in linear bandits1 paper raises it · 1 addresses it
Real-world systems often change over time, making static models ineffective for long-term decision-making.
- Optimal Contextual Pricing in Non-Stationary Environmentsraises · addresses
Balancing exploration and regret in pure exploration1 paper raises it · 1 addresses it
Exploration strategies must account for regret costs relative to a baseline, not just sample efficiency.
- SHPRR: An Algorithm for Pure Exploration under Constrained Regretraises · addresses
Optimizer-dependent precision limits in high-dimensional sensing1 paper raises it · 1 addresses it
Numerical precision can stall optimization in high-dimensional or ill-conditioned problems, limiting practical performance.
- The Precision Wall: An Optimizer-Dependent Boundary for Optimization under Power-Law Measurement Spectraraises · addresses
Adaptive path selection under mobility and energy constraints1 paper raises it · 1 addresses it
Mobile sensors must efficiently explore while respecting physical constraints like energy and path feasibility.
- Adaptive search with path-constrained mobile sensors using multi-arm banditsraises · addresses
Domain generalization with adversarial target domains1 paper raises it · 1 addresses it
Models trained on well-resourced domains often fail in underrepresented or adversarially chosen new domains.
- Rural Readiness: Domain Generalization with Adversarially Chosen Domainsraises · addresses

Named by an AI from these papers' abstracts.

Open problems

Recently funded

Topics in this field

linear bandits · optimal regret · bandits179 papers17 this week
sample complexity · complexity · vc dimension97 papers12 this week
policy gradient · optimal policy · reinforcement learning rl160 papers11 this week
stochastic gradient descent · stochastic optimization · convex optimization120 papers9 this week
online convex optimization · optimal regret · online convex64 papers7 this week

Topics in this field

Active contributors · 90 days

Active contributors

Activity · 12 weeks

Activity

Recent papers

All papers in Research

arXiv cs.LGOct 28
Planned Restlessness: Delayed Meta Bandits with Budgets
Sudipto Guha
We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets,…
PDF arXiv
arXiv cs.LGOct 28
Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
Igor Sokolov, Alexander Tyurin, Peter Richtárik
The empirical success of matrix-aware optimizers, such as Muon (Jordan et al., 2024) and Shampoo (arXiv:1802.09568), highlights the potential of non-Euclidean geometry for deep learning, including large language model (LLM) training. Despite this progress, the theoretical understanding of stochastic optimization in general normed spaces remains limited, particularly in distributed settings. We analyze minibatch stochastic gradient descent (SGD) for smooth nonconvex optimization with respect to an arbitrary norm on a finite-dimensional space. Using the framework of $κ$-regular normed spaces (arXiv:0809.0813), we derive high-probability oracle complexity bounds under a light-tail condition stated directly in the dual norm induced by the update norm. The bounds make the dependence on geometry explicit through the regularity constant $κ$ of the dual space. In the Euclidean case, our bound recovers the standard minibatch SGD rate up to logarithmic factors. For some non-Euclidean geometries and noise models, it is sharper than bounds obtained by converting a Euclidean noise assumption, reducing a linear dimension dependence to a logarithmic one. Building on this framework, we introduce…
PDF arXiv
arXiv cs.LGOct 28
Optimal Regret for Communication-Efficient Decentralized Online Learning
Sifan Yang, Wenhao Yang, Wei Jiang, Yuanyu Wan, Lijun Zhang
In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions,…
PDF arXiv
arXiv cs.AIOct 28
Game-Theoretic Foundations for Undiscounted Bisimulation Metrics
Matthew Zurek, Yudong Chen, Josiah P. Hanna
Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally,…
PDF arXiv
arXiv cs.LGOct 28
Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
Qiwei Di, Quanquan Gu
We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget $C$. Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, $\tilde O(\sqrt{d^3T} + dC)$ by Liu et al. (2024), is a factor $\sqrt{d}$ above the corruption-free rate in its leading term, and whether $\tilde O(d\sqrt{T} + dC)$ regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term…
PDF arXiv
arXiv cs.DSOct 28
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta, Edo Liberty, Cameron Musco +2
Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner…
PDF arXiv

Papers

Topics in this field

linear bandits · optimal regret · bandits179 papers17 this week
sample complexity · complexity · vc dimension97 papers12 this week
policy gradient · optimal policy · reinforcement learning rl160 papers11 this week
stochastic gradient descent · stochastic optimization · convex optimization120 papers9 this week
online convex optimization · optimal regret · online convex64 papers7 this week

Active contributors · 90 days

Recent papers

All papers in Research

arXiv cs.LGOct 28
Planned Restlessness: Delayed Meta Bandits with Budgets
Sudipto Guha
We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets,…
PDF arXiv
arXiv cs.LGOct 28
Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry
Igor Sokolov, Alexander Tyurin, Peter Richtárik
The empirical success of matrix-aware optimizers, such as Muon (Jordan et al., 2024) and Shampoo (arXiv:1802.09568), highlights the potential of non-Euclidean geometry for deep learning, including large language model (LLM) training. Despite this progress, the theoretical understanding of stochastic optimization in general normed spaces remains limited, particularly in distributed settings. We analyze minibatch stochastic gradient descent (SGD) for smooth nonconvex optimization with respect to an arbitrary norm on a finite-dimensional space. Using the framework of $κ$-regular normed spaces (arXiv:0809.0813), we derive high-probability oracle complexity bounds under a light-tail condition stated directly in the dual norm induced by the update norm. The bounds make the dependence on geometry explicit through the regularity constant $κ$ of the dual space. In the Euclidean case, our bound recovers the standard minibatch SGD rate up to logarithmic factors. For some non-Euclidean geometries and noise models, it is sharper than bounds obtained by converting a Euclidean noise assumption, reducing a linear dimension dependence to a logarithmic one. Building on this framework, we introduce…
PDF arXiv
arXiv cs.LGOct 28
Optimal Regret for Communication-Efficient Decentralized Online Learning
Sifan Yang, Wenhao Yang, Wei Jiang, Yuanyu Wan, Lijun Zhang
In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(ω^{-1/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $ρ\in(0,1)$ is the spectral gap of the communication matrix and $ω\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $Ω(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $ρ^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln T)$ for convex and strongly convex loss functions,…
PDF arXiv
arXiv cs.AIOct 28
Game-Theoretic Foundations for Undiscounted Bisimulation Metrics
Matthew Zurek, Yudong Chen, Josiah P. Hanna
Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally,…
PDF arXiv
arXiv cs.LGOct 28
Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
Qiwei Di, Quanquan Gu
We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget $C$. Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, $\tilde O(\sqrt{d^3T} + dC)$ by Liu et al. (2024), is a factor $\sqrt{d}$ above the corruption-free rate in its leading term, and whether $\tilde O(d\sqrt{T} + dC)$ regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term…
PDF arXiv
arXiv cs.DSOct 28
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta, Edo Liberty, Cameron Musco +2
Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner…
PDF arXiv

Activity · 12 weeks

Fields · AI · updated 41m ago

Linear bandits

Found by the topic model: linear bandits, policy gradient, stochastic gradient descent.

56papers this week−21.1% vs last week

All papers · 620 With code · 1

Newest Most relevant

400 papers this month

Open problems in Linear bandits

Handling non-stationary environments in linear bandits1 paper raises it · 1 addresses it
Real-world systems often change over time, making static models ineffective for long-term decision-making.
- Optimal Contextual Pricing in Non-Stationary Environmentsraises · addresses
Balancing exploration and regret in pure exploration1 paper raises it · 1 addresses it
Exploration strategies must account for regret costs relative to a baseline, not just sample efficiency.
- SHPRR: An Algorithm for Pure Exploration under Constrained Regretraises · addresses
Optimizer-dependent precision limits in high-dimensional sensing1 paper raises it · 1 addresses it
Numerical precision can stall optimization in high-dimensional or ill-conditioned problems, limiting practical performance.
- The Precision Wall: An Optimizer-Dependent Boundary for Optimization under Power-Law Measurement Spectraraises · addresses
Adaptive path selection under mobility and energy constraints1 paper raises it · 1 addresses it
Mobile sensors must efficiently explore while respecting physical constraints like energy and path feasibility.
- Adaptive search with path-constrained mobile sensors using multi-arm banditsraises · addresses
Domain generalization with adversarial target domains1 paper raises it · 1 addresses it
Models trained on well-resourced domains often fail in underrepresented or adversarially chosen new domains.
- Rural Readiness: Domain Generalization with Adversarially Chosen Domainsraises · addresses

Named by an AI from these papers' abstracts.