Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback

Abstract

In this paper, we first study the problem of combinatorial pure exploration with full-bandit feedback (CPE-BL), where a learner is given a combinatorial action space $\mathcal{X}\subseteq \{0,1{\}}^d$, and in each round the learner pulls an action $x\in \mathcal{X}$ and receives a random reward with expectation $x^{\top }\theta$, with $\theta \in {\mathbb{R}}^d$ a latent and unknown environment vector. The objective is to identify the optimal action with the highest expected reward, using as few samples as possible. For CPE-BL, we design the first {\em polynomial-time adaptive} algorithm, whose sample complexity matches the lower bound (within a logarithmic factor) for a family of instances and has a light dependence of ${\Delta }_{\min }$ (the smallest gap between the optimal action and sub-optimal actions). Furthermore, we propose a novel generalization of CPE-BL with flexible feedback structures, called combinatorial pure exploration with partial linear feedback (CPE-PL), which encompasses several families of sub-problems including full-bandit feedback, semi-bandit feedback, partial feedback and nonlinear reward functions. In CPE-PL, each pull of action $x$ reports a random feedback vector with expectation of $M_x\theta$, where $M_x\in {\mathbb{R}}^{m_x\times d}$ is a transformation matrix for $x$, and gains a random (possibly nonlinear) reward related to $x$. For CPE-PL, we develop the first {\em polynomial-time} algorithm, which simultaneously addresses limited feedback, general reward function and combinatorial action space, and provide its sample complexity analysis. Our empirical evaluation demonstrates that our algorithms run orders of magnitude faster than the existing ones, and our CPE-BL algorithm is robust across different ${\Delta }_{\min }$ settings while our CPE-PL algorithm is the only one returning correct answers for nonlinear reward functions.

arXiv commentAAAI2021

References in corpus (11)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Best-Arm Identification in Linear Bandits
• Gamification of Pure Exploration for Linear Bandits
• Top-k Combinatorial Bandits with Full-Bandit Feedback
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Online Dense Subgraph Discovery via Blurred-Graph Feedback
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Combinatorial Pure Exploration of Dueling Bandit
• Towards Optimal and Efficient Best Arm Identification in Linear Bandits
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting

Cited by in corpus (1)

• Best Arm Identification in Graphical Bilinear Bandits