- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers the stochastic matroid semi-bandit problem with Bernoulli rewards where multiple arms must be selected in each round and the selected arms must form a basis of an unknown matroid. The learner has independence oracle access to the matroid and receives individual samples at each arm-pull. There are arms and the matroid rank is . The paper proposes a general algorithm that uses expected total of (thus finite and polynomial) independence queries over the infinite horizon, uses memory of words, and achieves the logarithmic regret , with the optimal coefficient (where the matroid is known). On the other hand, the number of independence queries in previous algorithms may grow with the time horizon. The authors then consider a special case in which the mean rewards are distinct and improve the number of independence queries to under the same asymptotic regret. They also provide a worst-case lower bound of which matches the distinct-means algorithm when the rank is balanced (when and ).
Critical strengths
- The problem is interesting and precisely formulated.
- The results are substantive, specially the lower bound shows that the polynomial bound only a factor of away from being optimal in the general case.
Critical weaknesses
- The writing of the paper is rough specially in the introduction. I could not understand the introduction without first reading the rest of the paper.
Questions for authors
None
3 comments
I thank the authors for their response. I will keep the same positive score.
Thank you for letting us know so soon. We appreciate it.
Thank you for the positive evaluation and for the comment on the introduction. We agree: we used several terms (C⋆(μ), "certificate", "exchange partner") before defining them, and the most intuitive example appeared only in Section 5. We made three changes (in blue):
For the story behind the problem (why we count structural queries separately from reward samples), please see the general response and also our response to reviewer bMY6 for a clear motivation.
Thank you also for noting that the lower bound leaves only a factor of d in the general case. We agree that this gap under ties is the main open question, and closing it is a natural next step.
We hope our response has clearly addressed your concerns, and we are happy to address any additional questions.