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 · bandits182 papers20 this week
policy gradient · optimal policy · reinforcement learning rl164 papers14 this week
sample complexity · complexity · vc dimension98 papers13 this week
stochastic gradient descent · stochastic optimization · convex optimization123 papers12 this week
online convex optimization · optimal regret · online convex65 papers8 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 23
Amortized Thompson Sampling and Efficient Information-Directed Sampling for Simulator-Based Design
Michal Kobiela, Michael U. Gutmann
Thompson sampling is a widely used strategy for sequential decision-making under uncertainty, offering a principled way to balance exploration and exploitation. This strategy involves maximizing a target objective under a single sample drawn from the current belief over unknown quantities. Conventionally, this optimization is performed once the belief has been inferred from data, and it becomes computationally burdensome when many Thompson samples are required, especially in continuous action spaces. In this work, we introduce an approach that amortizes this process ahead of time, before any data is collected, so that an approximation of the full Thompson sampling distribution is available immediately once observations arrive. We employ this approach to solve the multi-round setting, involving sequential data acquisition and Thompson-sample recommendation across rounds. Beyond accelerating Thompson sampling, our approach enables efficient estimation of expected information gain about the optimal action. This can be used to select more informative Thompson samples or to obtain maximally informative designs with optimization. Combining this estimate of expected information gain…
PDF arXiv
arXiv math.OCOct 23
On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
Feiming Wang, Yutong He, Sulaiman Alghunaim, Kun Yuan
Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.
PDF arXiv
arXiv cs.LGOct 23
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Sajad Ashkezari, Shai Ben-David
We determine the optimal regret in agnostic multiclass online learning with arbitrary, possibly infinite, label spaces. For every hypothesis class of multiclass Littlestone dimension $d<\infty$, we prove a regret upper bound of $O(\min\{T,\sqrt{dT}\})$ over $T$ rounds, matching the known lower bound. This resolves a question of Hanneke et al. (2023) and extends the optimal binary regret bound of Alon et al. (2021). Our proof strengthens the one-sided expert cover of Hanneke et al. (2023) to a fractional cover. We combine this cover with a minimax reduction to a finite expert game, whose best-response rewards provide the disagreement bounds needed for chaining.
PDF arXiv
arXiv stat.MLOct 23
Conditional Flow Models for Offline Maximum Entropy Reinforcement Learning
Hao Cheng, Yuling Jiao, Lican Kang, Jerry Zhijian Yang, Chen Zhong
Offline maximum entropy reinforcement learning seeks to estimate the optimal soft action-value function $Q^*$ from a fixed dataset without further interaction with the environment. Although $Q^*$ is characterized by the soft optimal Bellman equation, the corresponding Bellman operator cannot be evaluated directly because both the reward distribution and the transition kernel are unknown. Consequently, estimating $Q^*$ requires the joint treatment of environment modeling and value function learning. We propose a framework that addresses these tasks separately. Conditional diffusion models based on probability flow ODEs estimate the conditional reward distribution and transition kernel. The resulting distributional estimators define a data driven approximation of the soft optimal Bellman operator, whose empirical Bellman residual is minimized over a class of deep neural networks to estimate $Q^*$. We establish nonasymptotic guarantees for the proposed method. For operator learning, we derive total variation error bounds for the conditional flow estimators that account explicitly for score estimation, numerical discretization, and terminal smoothing. For soft value learning,…
PDF arXiv
arXiv math.OCOct 23
A Dynamic Inventory Rationing Model for Last-Mile Delivery of Medication in Liberia's Community Health Program
Baris Ata, Yufan Chen, Robert Montgomery
We study the dynamic allocation of scarce medications in Liberia's community health program. A central warehouse supplies a health facility and the Community Health Assistants (CHAs) it supervises. When a CHA runs out of medication, patients are referred to the facility, incurring travel costs if they complete the referral and remain untreated otherwise. Allocating inventory to CHAs allows more patients to receive treatment without traveling, while retaining inventory centrally preserves flexibility to respond to uncertain demand. The allocation problem must balance these considerations while accounting for fairness across locations. We formulate this problem as a finite-horizon stochastic control problem whose objective combines the costs of referrals and untreated patients with a demand-weighted fairness utility. Because standard dynamic programming methods are computationally intractable in this setting, we develop a continuous-time approximation that involves controlling the drift rate of a reflected Brownian motion. We then adapt the deep splitting method, using deep neural networks to approximate the value function and its gradient and compute a dynamic allocation policy.…
PDF arXiv
arXiv cs.LGOct 22
Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
Ivan Viakhirev, Kirill Borodin, Grach Mkrtchian
Reporting the best of $M$ noisy, unbiased scores overstates the winner's value by up to $c\sqrt{V}$, where $V$ is the total noise variance and the sharp constant $c$ depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence ($\sqrt{(M-1)/M}$) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is $\sqrt{(M-1)/(2M)}$, and for pairwise nonnegatively correlated noise it is $(M-1)/M$; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.
PDF arXiv

Papers

Topics in this field

linear bandits · optimal regret · bandits182 papers20 this week
policy gradient · optimal policy · reinforcement learning rl164 papers14 this week
sample complexity · complexity · vc dimension98 papers13 this week
stochastic gradient descent · stochastic optimization · convex optimization123 papers12 this week
online convex optimization · optimal regret · online convex65 papers8 this week

Recent papers

All papers in Research

arXiv cs.LGOct 23
Amortized Thompson Sampling and Efficient Information-Directed Sampling for Simulator-Based Design
Michal Kobiela, Michael U. Gutmann
Thompson sampling is a widely used strategy for sequential decision-making under uncertainty, offering a principled way to balance exploration and exploitation. This strategy involves maximizing a target objective under a single sample drawn from the current belief over unknown quantities. Conventionally, this optimization is performed once the belief has been inferred from data, and it becomes computationally burdensome when many Thompson samples are required, especially in continuous action spaces. In this work, we introduce an approach that amortizes this process ahead of time, before any data is collected, so that an approximation of the full Thompson sampling distribution is available immediately once observations arrive. We employ this approach to solve the multi-round setting, involving sequential data acquisition and Thompson-sample recommendation across rounds. Beyond accelerating Thompson sampling, our approach enables efficient estimation of expected information gain about the optimal action. This can be used to select more informative Thompson samples or to obtain maximally informative designs with optimization. Combining this estimate of expected information gain…
PDF arXiv
arXiv math.OCOct 23
On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
Feiming Wang, Yutong He, Sulaiman Alghunaim, Kun Yuan
Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.
PDF arXiv
arXiv cs.LGOct 23
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Sajad Ashkezari, Shai Ben-David
We determine the optimal regret in agnostic multiclass online learning with arbitrary, possibly infinite, label spaces. For every hypothesis class of multiclass Littlestone dimension $d<\infty$, we prove a regret upper bound of $O(\min\{T,\sqrt{dT}\})$ over $T$ rounds, matching the known lower bound. This resolves a question of Hanneke et al. (2023) and extends the optimal binary regret bound of Alon et al. (2021). Our proof strengthens the one-sided expert cover of Hanneke et al. (2023) to a fractional cover. We combine this cover with a minimax reduction to a finite expert game, whose best-response rewards provide the disagreement bounds needed for chaining.
PDF arXiv
arXiv stat.MLOct 23
Conditional Flow Models for Offline Maximum Entropy Reinforcement Learning
Hao Cheng, Yuling Jiao, Lican Kang, Jerry Zhijian Yang, Chen Zhong
Offline maximum entropy reinforcement learning seeks to estimate the optimal soft action-value function $Q^*$ from a fixed dataset without further interaction with the environment. Although $Q^*$ is characterized by the soft optimal Bellman equation, the corresponding Bellman operator cannot be evaluated directly because both the reward distribution and the transition kernel are unknown. Consequently, estimating $Q^*$ requires the joint treatment of environment modeling and value function learning. We propose a framework that addresses these tasks separately. Conditional diffusion models based on probability flow ODEs estimate the conditional reward distribution and transition kernel. The resulting distributional estimators define a data driven approximation of the soft optimal Bellman operator, whose empirical Bellman residual is minimized over a class of deep neural networks to estimate $Q^*$. We establish nonasymptotic guarantees for the proposed method. For operator learning, we derive total variation error bounds for the conditional flow estimators that account explicitly for score estimation, numerical discretization, and terminal smoothing. For soft value learning,…
PDF arXiv
arXiv math.OCOct 23
A Dynamic Inventory Rationing Model for Last-Mile Delivery of Medication in Liberia's Community Health Program
Baris Ata, Yufan Chen, Robert Montgomery
We study the dynamic allocation of scarce medications in Liberia's community health program. A central warehouse supplies a health facility and the Community Health Assistants (CHAs) it supervises. When a CHA runs out of medication, patients are referred to the facility, incurring travel costs if they complete the referral and remain untreated otherwise. Allocating inventory to CHAs allows more patients to receive treatment without traveling, while retaining inventory centrally preserves flexibility to respond to uncertain demand. The allocation problem must balance these considerations while accounting for fairness across locations. We formulate this problem as a finite-horizon stochastic control problem whose objective combines the costs of referrals and untreated patients with a demand-weighted fairness utility. Because standard dynamic programming methods are computationally intractable in this setting, we develop a continuous-time approximation that involves controlling the drift rate of a reflected Brownian motion. We then adapt the deep splitting method, using deep neural networks to approximate the value function and its gradient and compute a dynamic allocation policy.…
PDF arXiv
arXiv cs.LGOct 22
Sharp Bounds on the Winner's Bias under Independent and Nonnegatively Correlated Noise
Ivan Viakhirev, Kirill Borodin, Grach Mkrtchian
Reporting the best of $M$ noisy, unbiased scores overstates the winner's value by up to $c\sqrt{V}$, where $V$ is the total noise variance and the sharp constant $c$ depends on how the noise is dependent. It was known only at the two extremes, arbitrary dependence ($\sqrt{(M-1)/M}$) and i.i.d. noise. We determine it for two classes in between: for independent, not identically distributed noise it is $\sqrt{(M-1)/(2M)}$, and for pairwise nonnegatively correlated noise it is $(M-1)/M$; for uncorrelated noise this answers the maximum version of an open question about the expected range. Explicit finite constructions attain both. As a corollary, the bias of the cross-validation estimator is bounded sharply within each class. All theorems are formally verified in Lean 4. Across 448 language-model and classifier selection pipelines, designs with per-candidate items realize a median 0.75 of the independent-class ceiling. At a fixed item budget, scoring all candidates on shared items is markedly less optimistic than giving each candidate its own items.
PDF arXiv

Active contributors · 90 days

Activity · 12 weeks

Fields · AI · updated 29m ago

Linear bandits

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

67papers this week+1.5% vs last week

All papers · 632 With code · 1

Newest Most relevant

408 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.