- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies Nash-value regret in unknown zero-sum matrix games where the opponent observes the learner’s mixed strategy before choosing a column. IC-RF combines restricted-face exploration with certified local refinement. For square games with a unique fully mixed equilibrium, it establishes a high-probability O(log Tloglog T) regret bound at fixed confidence, without knowing the instance difficulty parameters. Experiments examine regret, certification time, and component ablations.
Critical strengths
The extension from 2×2 bandit games to arbitrary-dimensional games within the stated class is a meaningful theoretical contribution. Handling several withheld columns requires accounting for exploration costs across changing restricted faces. The learn-or-earn argument and observable certificate provide a coherent solution without supplying the learner with the regularity parameters. This is the main reason I lean toward acceptance.
Critical weaknesses
The practical evidence is narrower than the theoretical scope. The main comparisons use 3×3 games, with the OpenSpiel subgames selected for favorable regularity. The noisy scaling experiments show no local entry for the tested d=3,4,5 settings by 640,000 rounds, and IC-RF matches Matrix–UCB on both Kuhn settings.
The best-response ablation logs also record no post-prelude restricted-face rounds for the full method. Thus, the main comparison primarily demonstrates the benefit of local control; empirical support for the global mechanism comes from the supplementary switching-face experiments.
Questions for authors
-
Could you provide a phase-level regret breakdown for the existing switching-face runs? This would help assess how much benefit comes from restricted-face play versus the prelude and local refinement.
-
Table 3 appears to report geometry for exact_matrix, whereas the experimental runner uses the episode-bank mean matrix. Please clarify this distinction and report the geometry of the evaluated matrix, particularly for Kuhn. Please also distinguish the table’s condition number from κ in the theorem.
3 comments
Q4
Could you provide a phase-level regret ... versus the prelude and local refinement.
A4: We reran the original eight settings with the same algorithm and matrices and recorded which phase incurred each round's regret. Each row below averages eight runs of 640,000 rounds. “Initial” is Matrix-UCB play. The next two columns split global play according to whether the opponent chose a column that had reached the current accuracy target (“Estimated”) or one that still needed observations (“Other”). A zero means that no round fell in that phase. Negative regret means the learner earned more in expectation than the full game's value against the columns actually played.
| Setting | Initial | Estimated | Other | Local | Total |
|---|---|---|---|---|---|
| RPS (mean) | -33,009.78 | 0 | 0 | -1,034.03 | -34,043.81 |
| RPS (noisy) | -24,861.26 | -21,080.75 | 60.58 | -6,130.29 | -52,011.72 |
| Blotto (mean) | -47,687.01 | 0 | 0 | -888.34 | -48,575.35 |
| Blotto (noisy) | -47,366.19 | 0 | 0 | -4,399.44 | -51,765.63 |
| Goofspiel (mean) | -16,706.11 | 0 | 0 | -805.63 | -17,511.73 |
| Goofspiel (noisy) | -16,682.16 | 0 | 0 | -871.58 | -17,553.74 |
| Kuhn (mean) | 1,144.34 | 0 | 47.14 | 0 | 1,191.48 |
| Kuhn (noisy) | 1,124.33 | 0 | 105.36 | 0 | 1,229.69 |
Noisy RPS is the setting where both sides of the proposed mechanism appear. Global play earned 21,080.75 above the game value over an average of 143,600 rounds against well-estimated columns. The cost on the other columns was 60.58 over about 187 rounds. Thus the global phase covered its own exploration cost. The initial and local phases earned additional payoff, 24,861.26 and 6,130.29 respectively. In Blotto and Goofspiel all gains came from initial and local play. In Kuhn, global sampling added to regret and local play never began.
We also replaced just the global policy on noisy RPS. Using Matrix-UCB there raised mean total regret by 12,021 relative to IC-RF. Solving the estimated game on the available columns and adding uniform exploration raised it by 2,681. Both increases remained significant after Holm correction across the 24 comparisons under this opponent. The second replacement changes the payoff estimates and the exploration rule together, so it tests that policy as a whole. We added the noisy RPS breakdown to Table 5 in Appendix A.5 and its interpretation to Section 5.3. Appendix A.6 describes the policy replacements.
Q5
Table 3 appears to report geometry ... distinguish the table’s condition number from κ in the theorem.
A5: You are right about the original table. We used the expected returns of policy pairs to help select each subgame. For the learning experiments, we saved 20,000 simulated returns per selected pair. In a noisy round the learner receives one return drawn uniformly with replacement from that pair's saved returns. The expected payoff in this experiment is therefore exactly the average of those returns. Returning that same average on a deterministic round lets us vary observation noise while holding the underlying matrix fixed. It also lets every method reuse the same simulated games.
In the files, the construction-time expectations are called exact_matrix and the averages used in play are called matrix. The original table used the former. We recalculated the parameters on the latter. Here are the values for the matrices actually played. “Min. prob.” is the smallest equilibrium probability across both players. “Deletion gap” is the smallest gain in the row player's guaranteed payoff from omitting one column.
| Game | Value | Min. prob. | Deletion gap | ||
|---|---|---|---|---|---|
| Blotto | 0.534351 | 0.290749 | 0.129088 | 3.954 | 2.182 |
| Goofspiel | 0.488649 | 0.234790 | 0.072862 | 8.910 | 4.630 |
| Kuhn poker | 0.543187 | 0.154088 | 0.008811 | 46.395 | 21.022 |
The last two columns measure different things. To rank candidate subgames, the construction code uses , the larger two-norm condition number of the two players' augmented equilibrium systems. The theorem uses , the larger infinity norm of their inverses, to bound how payoff errors affect the equilibrium estimate. Both numbers above are computed on the same evaluated matrix. Kuhn has the smallest deletion gap and the largest , so the theorem requires the highest payoff accuracy there to guarantee local entry. We corrected Table 3 in Appendix A.2 to report for the matrix used in play and revised the surrounding paragraphs to explain the selection score and the two feedback rules.
I thank the authors for the detailed rebuttal. The revised version largely addresses my core concerns, especially the clarifications on Table 3/κ and the phase-level regret breakdown. However, on presentation, I agree with Reviewer j2qG that the paper remains difficult to read. I therefore tend to keep my current score.
We sincerely thank the reviewer for comments. We address all five points below.
Q1
A1: Thank you for pointing out the limited experimental coverage. The original OpenSpiel subgames were selected. We first require a unique, fully mixed equilibrium, as assumed in the theorem, and then score candidates using their minimum equilibrium probabilities, deletion gaps, and the conditioning of the equilibrium equations. These parameters also affect the accuracy IC-RF needs before local learning can begin, so your concern about the favorable selection is well taken.
On these instances, all methods use the same matrices, feedback rules, and interaction budgets, with eight runs per setting. Across the original eight settings, IC-RF has lower mean regret than Matrix-UCB in five, identical regret in two, and higher mean regret in one. It also has lower mean regret than CoEBL and EXP3 in all eight. These comparisons show that IC-RF's design provides a payoff benefit on the selected games. After extending the noisy runs to 2.56 million rounds, its mean advantage over Matrix-UCB grows from 4.35 to 13.18 on RPS and from 2.61 to 8.10 on Blotto. The benefit in those two settings continues to accumulate with further interaction.
To examine dependence on favorable instance parameters, we also tested prescribed matrices while varying dimension, deletion gap, and observation noise, for a total of 128 runs. All deterministic runs reached local learning. Under Bernoulli feedback, all eight runs entered in only three of the eight settings. At a fixed payoff-separation parameter, increasing the dimension from 2 to 3 increased mean entry time from approximately 131,000 to 1,215,000 rounds. This shows why instance selection matters. Favorable parameters allow local learning to contribute earlier; larger dimensions or noisier feedback can keep the algorithm in its initial stage for much longer. Its tie with Matrix-UCB on Kuhn likewise reflects the fact that local learning never began there.
We have made the selection procedure explicit in Appendix A.2 and added the parameter experiments and longer-horizon comparisons in Section 5.2 and Appendices A.1 and A.3, explaining when the method improves regret and what limits its finite-horizon performance.
Q2
A2: With Bernoulli noise and a=0.4, the mean first round of local learning rose from 131,148 at d=2 to 1,214,714 at d=3. At d=2, reducing a to 0.2 delayed the mean to 550,962 rounds. All eight seeds reached local learning in each of these three settings. At d=3 with a=0.2, and in both settings at d=4 and 5, all eight runs ended before local learning began. The crosses at the horizon in the figure mark those unfinished waits.
The Kuhn tie has a direct explanation. IC-RF used its initial Matrix-UCB policy throughout every run in both original Kuhn settings. Even after extending noisy Kuhn to 2.56 million rounds, all eight runs still used that policy. The two methods therefore used the same policy throughout and had identical regret for each of the eight seeds, with a mean of 76.30. Kuhn also has the smallest increase in value on deleting a column (0.008811) and the largest equilibrium sensitivity (κ=21.022) among the three OpenSpiel matrices. Both make the proof's sufficient accuracy requirement tighter, consistent with the delay observed here. We added the entry times in Appendix A.1, the Kuhn parameters in Table 3 (A.2), and the longer Kuhn comparison in Section 5.2 and Table 4 (A.3).
Q3
A3: Your reading of the logs is correct. Across all eight best-response settings, every IC-RF round used either the initial Matrix-UCB policy or a local update. For example, on deterministic rock–paper–scissors (RPS) the mean regret of 9.619 breaks down into 9.544 in initial play and 0.075 in local play. Any difference from running Matrix-UCB throughout could therefore arise only after the local updates began.
A best response always chooses the column giving the announced strategy its lowest payoff. That payoff can be at most the full game's value, so this opponent gives the learner no opportunity to earn above that value. To test the other part of the method we used an opponent that periodically changes which column it omits, choosing a best response among the columns still available. This allows the learner both to profit while a column is absent and to incur a cost when it reappears. On noisy RPS, the mean gain during global play on well-estimated columns exceeded 21,000, while sampling columns that still needed observations cost about 61. We clarified the best-response results in Section 5.2 and the role of the changing opponent in Section 5.3 and Appendix A.5.