Summary
The authors consider a framework to solve the bandit problem by means of the minimax problem, which has been rapidly developed in recent years.
Among them, the paper focuses on the decision-estimation coefficient (DEC).
The DEC was developed in a series of studies by Foster+ and is known to characterize the upper and lower bound of the worst-case regret in a general class of bandit problems.
The Estimation-to-Decisions (E2D) framework, an algorithm using DEC, determines action selection probabilities based on DEC.
However, the algorithm based on offset DEC, which is an existing DEC, is expected to have conservative performance because it needs to determine the tradeoff parameter based on the regret upper bound.
Furthermore, the recently developed constrained DEC does not require a tradeoff parameter, but has the problem that the strongly duality of a Lagrangian saddle point fails.
To solve these problems, the authors propose average-constrained DEC, a formulation in which the feasible region of the max player in the constrained DEC formulation is relaxed.
This eliminates the need to determine the tradeoff parameter based on the regret upper bound while maintaining the good properties of the optimization problem, resulting in an anytime algorithm.
Furthermore, by considering a variant of average-constrained DEC, the authors show that an improved rate can be obtained for high-dimensional linear bandits, and this is confirmed through actual numerical experiments.
Strengths
- Overall, the paper is written in a very clear manner. In particular, it clearly summarizes the characteristics of the DECs proposed so far.
- It clearly points out the problems of existing algorithms and presents simple solutions to solve them.
- The authors devise a specific procedure for obtaining a regret upper bound not only when the model is discrete, but also when linear bandits ( possibly with side observations) are used.
- While no numerical experimental evaluation of the DEC has been done so far, the effectiveness of the DEC is demonstrated through numerical experiments in the high dimensional linear bandits.
Weaknesses
- Abstract and introduction are slightly misleading, as it appears that the average-constrained DEC results can be used directly to obtain results for high-dimensional linear bandits.
- Although partial monitoring is mentioned in l120-125, the authors are actually solving the problem in a setting where rewards are also observed (or can be assumed to be included), as described in Example 1.2. The authors do not explain to what extent there is a gap with partial monitoring, and it is not clear to what extent the proposed algorithm is applicable to partial monitoring.
- As mentioned by the authors, there are other approaches to characterizing sequential decision problems by minimax problems, such as IDS and ExpByOpt. A brief explanation of why the focus is on DEC would be desirable.
Minor issues and typos:
- l31: $M_f$ should be $M_{f^*}$
- the meaning of "localization" was unclear and it would be better to explain the meaning in short.
- In footnote 3, $\max_{f \in co(\mathcal{M})}$ is $\max_{f \in \mathcal{F}}$?
Questions
- While the original DEC is formulated based on the Hellinger distance, this paper uses KL divergence for simplicity. What are the advantages and disadvantages that arise from these?
- (e.g.,l169) The meaning of telescope was unclear. Can you explain the meaning of this?
- (after l244) For the part of inequality (i), shouldn't the second term of max contains $\mathrm{dec}^{ac}_{\epsilon_t}(\hat{f}_t)$? (The order and the last equation are correct.)
- (l226) Why is the assumption "$\max_f \{ \epsilon^2 \mathrm{dec}^{ac}_{\epsilon} (f)\}$ is non-decreasing in $\epsilon$" reasonable? Is there any exception?
- Foster+2022 also devised DEC in the adversarial setting. Is the same kind of reparameterization possible in adversarial setting as in the paper? Is there any exception?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.