Efficient Matroid Bandit Linear Optimization Leveraging Unimodality

• URL: http://arxiv.org/abs/2512.00605v1
• Date: Sat, 29 Nov 2025 19:41:13 GMT
• Title: Efficient Matroid Bandit Linear Optimization Leveraging Unimodality
• Abstract summary: This paper sheds a new light on the matroid semi-bandit problem by exploiting its underlying unimodal structure.<n> Experiments conducted on various matroid benchmarks show (i.e., no loss in regret compared to state-of-the-art approaches) no loss in regret compared to state-of-the-art approaches.
• Score: 3.620281545470954
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the combinatorial semi-bandit problem under matroid constraints. The regret achieved by recent approaches is optimal, in the sense that it matches the lower bound. Yet, time complexity remains an issue for large matroids or for matroids with costly membership oracles (e.g. online recommendation that ensures diversity). This paper sheds a new light on the matroid semi-bandit problem by exploiting its underlying unimodal structure. We demonstrate that, with negligible loss in regret, the number of iterations involving the membership oracle can be limited to \mathcal{O}(\log \log T)$. This results in an overall improved time complexity of the learning process. Experiments conducted on various matroid benchmarks show (i) no loss in regret compared to state-of-the-art approaches; and (ii) reduced time complexity and number of calls to the membership oracle.

Related papers

• Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning [37.15283418677639]
  Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner.<n>We replace the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization oracle.<n>We show that our algorithm reduces the total query complexity down to $O(Td_mathrmVC+1)$ while perfectly preserving near-optimal expected regret.
  arXiv  Detail & Related papers  (2026-05-08T02:41:23Z)
• Matroid Algorithms Under Size-Sensitive Independence Oracles [19.61677355524952]
  Matroid algorithms assume that each independence query can be answered in constant time, regardless of the size of the queried set.<n>In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set.<n>We introduce a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$.
  arXiv  Detail & Related papers  (2026-04-30T20:26:35Z)
• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  This paper is in the field of sequential Multi-Armed Bandits (MABs)<n>We study a particular case of the rested bandits in which the arms' expected reward is monotonically non-decreasing and concave.<n>We empirically compare our algorithms with state-of-the-art methods for non-stationary MABs over several synthetically generated tasks and an online model selection problem for a real-world dataset.
  arXiv  Detail & Related papers  (2024-11-06T22:00:46Z)
• Accelerating Matroid Optimization through Fast Imprecise Oracles [40.94053997358159]
  We analyze practical algorithms which only use few clean queries w.r.t. the quality of the dirty oracle. Notably, we prove that our algorithms are, in many respects, best-possible. We outline extensions to other matroid oracle types, non-free dirty oracles and other matroid problems.
  arXiv  Detail & Related papers  (2024-02-05T07:14:18Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need [15.113053885573171]
  We present a new algorithm based on posterior sampling for learning in constrained Markov decision processes (CMDP) in the infinite-horizon undiscounted setting. The algorithm achieves near-optimal regret bounds while being advantageous empirically compared to the existing algorithms.
  arXiv  Detail & Related papers  (2023-09-27T15:48:36Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  We study the $K$ contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes emphpreference-based feedback suggesting that one decision was better than the other. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works.
  arXiv  Detail & Related papers  (2021-11-24T07:14:57Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  We propose a formulation for robust non-rigid registration based on a globally smooth robust estimator for data fitting and regularization. We apply the majorization-minimization algorithm to the problem, which reduces each iteration to solving a simple least-squares problem with L-BFGS.
  arXiv  Detail & Related papers  (2020-04-09T01:45:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.