Research map / Bandits and online learning / Multi-armed bandits
Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces CMAB-MT, a combinatorial bandit framework with multivariate arm outcomes and probabilistic arm triggering, with a 1-norm smoothness condition and the CUCB-MT algorithm, and applies it to episodic RL and probabilistic maximum coverage for goods distribution to obtain matching or improved regret bounds.
Problem
Existing combinatorial bandits with probabilistically triggered arms treat each arm outcome as univariate, so they cannot exploit the statistical structure of multivariate outcomes such as transitions in episodic RL or indivisible goods distribution, leading to suboptimal regret.
Approach
Generalizes CMAB-T to d-dimensional multivariate arm outcomes, defines a weighted 1-norm triggering-probability-modulated smoothness condition, builds action-dependent confidence regions, and models episodic RL as a CMAB-MT instance where each transition kernel is an arm and occupancy measures are triggering probabilities.
Key results
- Episodic RL via CUCB-MT achieves tilde O(sqrt(H^4 S^2 A T)) regret with a simple constant-weight smoothness condition, and O(sqrt(H^3 S A T log(SAHT))) with the value-function-based MTPM+ condition, matching the minimax lower bound up to log factors.
- For PMC-GD, the framework improves the CUCB-T regret by a factor of tilde O(sqrt(V)) to tilde O(sqrt(k|U||V|T)), and variance-adaptive methods by tilde O(sqrt(|V|/k)).
- Gap-dependent regret for episodic RL scales with O(log T), and the framework recovers the CMAB-T 1-norm TPM bound tilde O(B_1 sqrt(mKT)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use value-function-related MTPM+ weights and variance-aware confidence regions instead of constant weights | CUCB-MT for episodic RL · Episodic RL | regret upper bound: \tilde{O}(\sqrt{H^4S^2AT}) -> O(\sqrt{H^3SAT\log (SAHT)}+H^3S^2A\log^{3/2} (SAHT)) | Helped |
| Apply sharp CMAB analysis to the value-function-weighted episodic RL method | CUCB-MT for episodic RL · Episodic RL | leading regret term: O \left(\sqrt{H^3SAT\log^5 (SAHT)}\right) -> O\left(\sqrt{H^3SAT\log (SAHT)}\right) | Helped |
| Use multivariant arms for indivisible-goods outcomes instead of the CUCB-T formulation | CUCB-MT for PMC-GD · PMC-GD | regret upper bound: \tilde{O}(\sqrt{k|U||V|^2T}) -> \tilde{O}(\sqrt{k|U||V|T}); factor of \tilde{O}(\sqrt{V}) | Helped |
| Use CUCB-MT for PMC-GD instead of variance-adaptive algorithms | CUCB-MT · PMC-GD | regret upper bound: \tilde{O}(\sqrt{|U||V|^2T}) -> \tilde{O}(\sqrt{k|U||V|T}); factor of \tilde{O}(\sqrt{|V|/k}) | Helped |
Surprising findings
- Episodic RL can be treated as a CMAB-MT instance and attains minimax-optimal leading regret, suggesting RL is not significantly harder than CMAB-MT in this sense.
Limitations
- PMC-GD joint oracle is NP-hard, so a pseudo-reward upper bound is used, adding an extra regret term.
- Analysis is theoretical with no empirical experiments.
- Episodic RL results assume tabular setting with known rewards and state-action-step arms; extension to function approximation is left open.
Experimental setup
Metrics: gap-dependent regret gap-independent regret approximate regret
Baselines: CUCB-T UCRL2 UCBVI Zhang et al. variance-adaptive CMAB-T algorithm Zhang et al. gap-dependent clipping RL algorithm
Builds on: CMAB-T UCRL2 UCB-VI Azar et al. optimistic value iteration CUCB
Closest papers by meaning
- Offline Learning for Combinatorial Multi-armed Bandits (ICML 2025 · similarity 0.89)
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.87)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.87)
- Global Rewards in Restless Multi-Armed Bandits (NeurIPS 2024 · similarity 0.86)
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.86)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.