- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper considers a two-player matrix game with random reward revelations and seeks to minimize the expected pseudo-regret that benchmarks against the maximin matrix entry (reward mean). It proposes a combined framework of UCB and FTRL to achieve the best-of-three-worlds type of bounds in Theorem 1, and provides a lower bound for the bound with respect to the revelation frequency. In addition, it gives an illustrative example in Section 5 for a two-action game, where the dependence on the revelation frequency can be further improved.
Critical strengths
- This work achieves three types of upper bounds simultaneously in one algorithm. Although the combination is not delicate, it is indeed effective.
- The illustrative example in Section 5 is interesting and implies a direction to be studied further.
Critical weaknesses
- The presentation is overall less than satisfying: some of the writing is clearly not polished (such as Line 351 "For , , ..."), some of it is overwhelmed with unnecessarily detailed technical description and computation (such as Section 4), and some leaves core pieces of the only algorithm to the appendix (the FTRL to Appendix B). In particular, I would appreciate if the authors could give high-level explanations before or amidst the technical details throughout the paper and if they could formally introduce the FTRL in the main text (it is not even written as a clear algorithm in the appendix).
- The example in Section 5 is way too "toy" to be an illustrative example for exploiting the column frequency estimation to further optimize the upper bound. Importantly, there is not a right-to-the-point summary that gives the spirit of this example (correct me if I miss it, but I only find computations of the example in Section 5). If I understand correctly, it is saying: If the opponent plays col 2 frequently enough to make row 2 attractive, then the regret incurred is nonpositive and offsets future regret; otherwise, it is clear that row 1 is safe and the regret is therefore low. Equally importantly, this section should include a claim that extends this idea to all or a family of two-action games and use the current example as a special case, for the completeness of this work. Otherwise it looks like a preliminary result of this direction as it is now.
Questions for authors
- Can the authors give clear high-level descriptions of the key ideas, in Section 3, 4, and 5, and include them in later revision?
- Can the authors address my concerns in the weaknesses above?
- Can the authors provide a more general statement for the idea in the two-action example in Section 5?
Response to Reviewer prHh
Thank you for pointing to the missing step in the explanation of Section 5. Your interpretation of the frequent-column case is correct. In the other case the learner still needs to establish a payoff gap from noisy observations. Here is the argument we would put before the calculations.
A statement for a family of two-action games. Suppose the two rows are (v,v+b) and (v−a,v+c) with a,c>0 and b≥0. The first row guarantees v. For a common column-2 frequency θ, the second row's deficit relative to v is d(θ)=a−(a+c)θ. The first row's advantage over it is g(θ)=d(θ)+bθ. Two consequences explain the example. If the second row matches or beats the first, its deficit is nonpositive. If θ≤a/[2(a+c)], the first row has a payoff advantage of at least a/2. Between these cases, any positive deficit is at most the payoff advantage. This also explains why the sign of regret in (2) matters.
For an adaptive opponent, the comparison needs the same frequency for both rows. On rounds when the safe row leads and the other row is eligible, let W be the sum of the other row's play probabilities and O their sum on column-2 rounds. For W>0 take θ=O/W. The two estimates in (18) use exactly these weights. In (17), a=α, b=β, and c=1/2−α, so Wd=αW−O/2 and Wg=Wd+βO. Rewards control Wg through (20). Revealed frequencies help recover the first-column payoff through (19). When sufficiently many observations accumulate, the confidence intervals exclude the losing alternative. The payoff identities above hold across this larger family. The rate in Theorem 2 uses the specific payoffs in (17).
How Sections 3 and 4 fit together. The leader is the row with the most optimistic estimate of its guaranteed payoff. Assigning it at least half the probability makes its reward observable often enough to test that estimate. The remaining probability lets eligible rows challenge it. Every round provides a reward for this comparison. A revealed column also identifies a matrix entry, so eventually a row can be ruled out as a challenger on the strength of a particular column. Equation (11) separates the cost of the leader/reference play from the cost of the challengers. At a strict saddle, playing the safe row off the saddle column earns a surplus that absorbs part of the comparison cost. For the entry bound, (16) instead counts losses on labeled rounds and uses independent revelation to translate the count into total expected regret.
The FTRL step. In Algorithm 1 the input to FTRL is the vector ut of estimated losses relative to the leader, whose conditional mean is given in (10). With G=∑s<tus, it chooses xt=argminx∈Δm(⟨G,x⟩+∑iλtiF(xi)−64∑ilogxi),zti=T+1Txti+1/m, where F(x)=−2x+(1−x)log(1−x)+x. The update starts at λ1i=16 and changes only the coefficient of the sampled feedback coordinate, by (B.15). Putting this optimization and its update together in one main-text algorithm box, and moving the constant calculations to the appendix, would make Algorithm 1 easier to follow.
Finally, line 351 uses the payoff range. Every positive gap Δ=v−Aij is at most 2, so each such entry contributes 1/Δ≥1/2 to Cc. This is what allows the confidence-failure term in (16) to be absorbed when there is a positive gap.