acceptodds
Under review as a conference paper at ICLR 2027

When Less Is More: Polylogarithmic Nash-Value Regret in Bandit Matrix Games

Abstract

In an unknown zero-sum matrix game, an adaptive opponent can choose which payoff column the learner observes. Under informed-bandit feedback, the opponent sees the learner's mixed row strategy before choosing a column; the learner then observes that column and one sampled payoff. Existing polylogarithmic Nash-value regret guarantees for this feedback model cover games. We obtain such a guarantee for square games of any dimension with a unique, fully mixed equilibrium. Our algorithm, Instance-Certified Restricted-Face Learning (IC-RF), plays against the columns it has learned well enough. If the opponent withholds other columns, this restricted game yields a value surplus; if those columns appear, the learner gains samples. A multiscale ledger uses the surplus to finance learning across accuracy levels without knowing the game's separation parameters. An observable saddle certificate then starts local refinement. At any fixed confidence level, the resulting high-probability Nash-value regret is , with a constant polynomial in the instance difficulty parameters. Experiments under best-response opponents show lower finite-horizon regret than established bandit baselines in most tested settings, while revealing slow certification in some higher-dimensional noisy games.

Primary area:
learning theory
Keywords:
matrix games, Nash-value regret, online learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_sRE5OpenReview ↗
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
  1. 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.

  2. 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

We sincerely thank the reviewer for comments. We address all five points below.

Q1

The practical evidence is narrower than ... subgames selected for favorable regularity.

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

The noisy scaling experiments show ... Matrix–UCB on both Kuhn settings.

A2: With Bernoulli noise and a=0.4a=0.4, the mean first round of local learning rose from 131,148 at d=2d=2 to 1,214,714 at d=3d=3. At d=2d=2, reducing aa to 0.2 delayed the mean to 550,962 rounds. All eight seeds reached local learning in each of these three settings. At d=3d=3 with a=0.2a=0.2, and in both settings at d=4d=4 and 55, 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\kappa=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

The best-response ablation ... the supplementary switching-face experiments.

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.

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.

SettingInitialEstimatedOtherLocalTotal
RPS (mean)-33,009.7800-1,034.03-34,043.81
RPS (noisy)-24,861.26-21,080.7560.58-6,130.29-52,011.72
Blotto (mean)-47,687.0100-888.34-48,575.35
Blotto (noisy)-47,366.1900-4,399.44-51,765.63
Goofspiel (mean)-16,706.1100-805.63-17,511.73
Goofspiel (noisy)-16,682.1600-871.58-17,553.74
Kuhn (mean)1,144.34047.1401,191.48
Kuhn (noisy)1,124.330105.3601,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.

GameValueMin. prob.Deletion gapCselC_{\rm sel}κ\kappa
Blotto0.5343510.2907490.1290883.9542.182
Goofspiel0.4886490.2347900.0728628.9104.630
Kuhn poker0.5431870.1540880.00881146.39521.022

The last two columns measure different things. To rank candidate subgames, the construction code uses CselC_{\rm sel}, the larger two-norm condition number of the two players' augmented equilibrium systems. The theorem uses κ\kappa, 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 κ\kappa, so the theorem requires the highest payoff accuracy there to guarantee local entry. We corrected Table 3 in Appendix A.2 to report κ\kappa 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.

Reviewer_XH7jOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

It is a zero-sum matrix game. The game has an unknown, fixed payoff matrix A∈[0,1]d×dA\in[0,1]^{d\times d}; the learner chooses rows, and the opponent chooses columns, with d≥2d\ge2 actions each. In round tt, the learner first publishes a mixed row strategy pt∈Λdp_t\in\Lambda_d. Then the opponent chooses a column jt∈[d]j_t\in[d]. The learner then draws itp˜ti_t\~p_t and observes jtj_t and one payoff Yt∈[0,1]Y_t\in[0,1]. Existing polylogarithmic Nash value regret guarantees for this feedback model cover 2×2 games. The authors obtain such a guarantee for square games of any dimension with a unique, fully mixed equilibrium.

Critical strengths
  • Existing polylogarithmic Nash value regret guarantees for this model cover 2×2 games. The authors extend such a guarantee for square games of any dimension with a unique, fully mixed equilibrium.
  • The paper develops a mechanism for exploiting the opponent's control over feedback. If the opponent withholds columns, the learner can exploit the higher value of the restricted game. If those columns are played, the learner acquires information.
Critical weaknesses
  • The main result requires a square payoff matrix with a unique equilibrium in which both players assign strictly positive probability to every action (both equilibrium strategies have full support).
  • The polylogarithmic regret guarantee may hide enormous constants.
Questions for authors

The polylogarithmic regret guarantee may hide enormous constants. Please analyze the dependence on Γcert\Gamma_{\mathrm{cert}}, the dimension dd, and the instance-separation parameters, and characterize the crossover horizon.

1 comment

We sincerely thank the reviewer for their comments. We address both points below.

Q1

The main result requires a square payoff matrix with a unique equilibrium ... (both equilibrium strategies have full support).

A1: Our fast-rate result assumes a square matrix with a unique, fully mixed equilibrium. These assumptions enter two steps of the proof.

First, we use the extra payoff available when the opponent temporarily avoids some columns to cover the cost of exploring the others. Uniqueness and full support of the column player's equilibrium strategy ensure that deleting any column strictly increases the row player's guaranteed payoff. If two columns are identical, for example, deleting either one leaves that payoff unchanged, and this source of compensation for exploration disappears.

Second, when updating near an estimated equilibrium, the learner needs continued opportunities to sample every row and a bound on how payoff-estimation errors move the equilibrium strategy. Full support of the row player's strategy provides positive sampling probabilities. For a square matrix, a unique, fully mixed equilibrium also makes the augmented equilibrium systems invertible, which allows us to bound this movement. The minimum equilibrium probabilities, deletion gap, and sensitivity of the equilibrium equations are therefore difficulty parameters determined by the instance. They affect the coefficient in the regret bound, and the learner need not know them in advance.

This class includes identity games of arbitrary dimension and shifted-and-scaled rock–paper–scissors, as well as sufficiently small payoff perturbations of these games. More generally, we prove that every game in the class retains a unique, fully mixed equilibrium under sufficiently small perturbations. The result thus applies to a continuously varying family of games. Extending the analysis to equilibria that assign zero probability to some actions or to games with multiple equilibria remains an open problem. We also clarified the role of the assumptions in Section 4.4 of the revised manuscript and gave an explicit perturbation radius in Appendix J.

Q2

The polylogarithmic regret guarantee may hide enormous constants. ... Please analyze the dependence on Γcert\Gamma_{\rm cert}, the dimension dd ... and characterize the crossover horizon.

A2: At 640,000 rounds and 95% confidence, the explicit bound on Blotto is about 1.55×10171.55\times10^{17}, while bounded payoffs give RT≤640,000R_T\le640{,}000.

The large coefficient comes in part from the accuracy sufficient to guarantee the switch to local learning. Write Γcert\Gamma_{\rm cert} for this accuracy, measured by the largest uncertainty radius of any payoff entry. Estimating one entry to accuracy ε\varepsilon costs about L/ε2\mathcal L/\varepsilon^2 observations, where L\mathcal L is the logarithmic confidence factor. A row that still needs samples may be played with probability only ε/d\varepsilon/d. Combining these costs across columns gives a global term of order d2L/Γcert3d^2\mathcal L/\Gamma_{\rm cert}^3.

To spell out the instance dependence, let ρ\rho and τ\tau be the smallest row and column equilibrium probabilities, Δdel\Delta_{\rm del} the smallest increase in value from deleting one column, and κ\kappa the sensitivity of the equilibrium equations. With κˉ=max⁡1,κ\bar\kappa=\max\\{1,\kappa\\}, that global term is O(κˉ3Lmax⁡d5, d7/2/ρ3, d2/τ3, d5/Δdel3)O(\bar\kappa^3\mathcal L\max\\{d^5,\,d^{7/2}/\rho^3,\,d^2/\tau^3,\,d^5/\Delta_{\rm del}^3\\}). A small deletion gap or a rarely played equilibrium action can therefore matter even in a three-by-three game.

For the crossover, we compare the full explicit bound, including local learning, with the unit-coefficient reference dT\sqrt{dT}. The table reports log⁡10T\log_{10}T where they cross. Bounds for specific algorithms also involve their constants and logarithmic factors.

GameSufficient radiusBound at 640,000log⁡10T\log_{10} T at crossing
Blotto3.081×10−43.081\times10^{-4}1.55×10171.55\times10^{17}34.11
Goofspiel8.197×10−58.197\times10^{-5}8.22×10188.22\times10^{18}37.57
Kuhn poker2.183×10−62.183\times10^{-6}4.35×10234.35\times10^{23}47.04

These calculations show that our explicit regret bound is conservative at the experimental horizons. On noisy RPS and Blotto, IC-RF begins local learning much earlier than the uniform sufficient condition would guarantee, and its observed regret is substantially smaller than the bound. This suggests room to tighten the analysis so that it better reflects the algorithm’s finite-time behavior.

Section 4.4 now explains the cubic dependence. Appendix C expands the instance factors, evaluates the full bound on the three matrices, and explains the difference between the sufficient threshold and the test used in play.

Reviewer_j2qGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper examines an interaction between a learner and an adaptive opponent in an unknown zero-sum matrix game. Existing work has established polylogarithmic Nash-value regret guarantees in a certain bandit feedback model, but only applied to 2x2 games. The main result of this paper is to extend this guarantee to any zero-sum game with a square payoff matrix and a unique, fully mixed equilibrium.

Critical strengths

On the positive side, the main result obtained in this paper is technically non-trivial and to my knowledge new. I'm familiar with the earlier paper that was tackling the 2x2 case, and it's clear that going beyond the 2x2 case is very challenging. As a result, I believe that some people in the ML community will find this to be an interesting result. More broadly, there has been much research obtaining improved regret guarantees in the full-information setting, but the bandit feedback is more challenging. Extending the scope of such results to meaningful notions of regret (such as the Nash-value regret considered in this paper) is worthwhile. The paper also conducts some experiments, showing that the new algorithm is not just of theoretical interest, but also performs well empirically.

Critical weaknesses

The main issue is that the writing in the current manuscript is of low quality. Even though I'm an expert in this area, I was having a hard time following the text throughout the paper. It routinely uses non-standard terms, even in the introduction, without any explanation. For example, here are some indicative sentences I couldn't parse at all from the introduction:

  • "A multiscale ledger uses the surplus to finance learning across accuracy levels without knowing the game’s separation parameters."
  • "It tracks the value of observed column faces across accuracy scales, then enters local refinement only after an observable saddle certificate succeeds."

The paper also fails to provide an intuition behind the main result. The basic tension is clear, already from the paper dealing with the 2x2 case. But this paper introduces many new components, which appear to come out of thin air, without an intuitive explanation. The paper also lacks in motivating the problem. I know the Nash-value regret has been introduced before, but I wanted to see a concrete motivation as to why one should care about this particular metric. A final limitation is that, experimentally, the improvement relative to matrix-UCB is very marginal, so from a practical standpoint, the paper is incremental.

Overall, the exposition of the paper is not good enough for publication. Using AI tools to assist is perfectly fine, but the paper is intended to be read by other human researchers. The technical insights need to be more accessible, and a human should be able to follow the logic of the text. I believe that with major rewriting, this paper could be strong enough for a publication in a future venue, but is not ready for ICLR.

Questions for authors

Two questions for the authors:

  • What are the obstacles in extending the result beyond the assumption of having a unique, fully mixed equilibrium?
  • Some of the experiments are conducted on extensive-form games. My understanding was that the main theoretical result only applies to normal-form games. Can the authors comment on how their approach can be applied to the extensive form?
3 comments

We sincerely thank the reviewer for their comments. We address all six points below.

Q1

It routinely uses non-standard terms, even in the introduction, without any explanation. ... "A multiscale ledger uses the surplus ... without knowing the game’s separation parameters." ... "It tracks the value of observed column faces ... after an observable saddle certificate succeeds."

A1: In the 3×33\times3 identity game from the introduction, the most the row player can guarantee is an expected payoff of 1/31/3 per round when the opponent can choose any of the three columns. Now suppose the opponent keeps choosing only the first two. Playing the first two rows with equal probability earns 1/21/2 against either column. The extra 1/61/6 on rounds when the learner uses this mixture can cover the cost of occasionally trying the third row, which earns zero against both of those columns. This is what the first passage meant by a “ledger.”

The “certificate” in the second passage is the test IC-RF uses to decide when it can start playing near the equilibrium it has estimated. Even a small error in the payoffs can sometimes change the equilibrium strategy substantially. IC-RF uses the uncertainty intervals around its payoff estimates to bound how far the true equilibrium strategy could be from the one it computed. It also checks that the strategies it would play near that estimate still give every row enough probability to keep collecting observations when the opponent plays a column. Once the test passes, IC-RF begins updating its strategy near the estimated equilibrium. We revised the discussion of the 3×33\times3 example in the introduction to explain how the extra payoff covers exploration costs, and the description of the switching rule in Section 4.2 to explain when local updates begin. We have also revised other relevant passages in the abstract, introduction, and method section.

Q2

The paper also fails to provide an intuition behind the main result. ... many new components ... without an intuitive explanation.

A2: We actually intended the 3×33\times3 identity-game example in the original introduction to illustrate this intuition. We have now expanded the explanation to clarify how the example motivates the algorithm’s components. When the opponent plays only the first two columns, mixing equally over the first two rows guarantees a payoff of 1/21/2 against either column, compared with the value of 1/31/3 that the row player can guarantee against all three columns.

Suppose the opponent plays only the first two columns for a long time. The learner could try every row a thousand times and still obtain no observation of the third column. Yet it may already know enough to choose a good mixture against the first two. Waiting for an accurate estimate of the entire matrix would waste that opportunity. This is why IC-RF uses the columns it has estimated well enough to guide play. It also leaves some probability on rows that still need samples, so it can learn more about an unfamiliar column when that column appears again.

How accurate do the estimates need to be? If omitting a column raises the value only slightly, even a small estimation error can erase the gain. The size of that gain depends on the unknown matrix. IC-RF therefore tightens its accuracy target in stages. The key step in our proof is to account for the extra payoff earned against familiar columns together with the cost of learning other columns more accurately later. This lets us control cumulative regret even when the opponent waits a long time before changing columns.

Local updates serve a different purpose. Once the data locate the equilibrium accurately enough, the learner can compare strategies near that estimate. If two strategies assign nearly the same probability to a row, an error in that row’s payoff has little effect on their relative payoffs. This is the reason for checking the stability of the equilibrium estimate before switching. To bound regret during a local stage, the proof considers the least frequently played column. If it was rare, the higher payoff available on the remaining columns helps cover the loss. If even that column was frequent, every column has offered enough sampling opportunities to refine the estimates. This bounds the regret accumulated within each local stage, and there are at most O(log⁡T)O(\log T) such stages. Together with confidence intervals valid throughout play, this gives O(log⁡Tlog⁡log⁡T)O(\log T\log\log T) regret at fixed confidence for each fixed square game with a unique, fully mixed equilibrium, with a constant that depends on the game.

We have also included these explanations in the revised manuscript, following the 3×33\times3 example in the introduction and in the descriptions of global learning (Section 4.1) and local updates (Section 4.2).

Q3

The paper also lacks in motivating the problem. ... why one should care about this particular metric.

A3: We want to know how much payoff the learner gives up by having to learn the game. A player who already knows the matrix could guarantee its mixed-strategy value, even against an opponent who sees its announced distribution. That gives a natural payoff to compare against.

For example, in the 2×22\times2 identity game, playing either row deterministically lets the opponent choose the other column and hold the payoff to zero. Yet tossing a fair coin between the two rows guarantees 1/21/2 per round. A learner earning zero throughout would have zero regret relative to the best pure-row guarantee, despite missing half a unit of attainable payoff every round. Nash-value regret records that shortfall as T/2T/2 after TT rounds. We revised the introduction to motivate this choice. Section 3 gives the two definitions and their exact relationship.

Q4

experimentally, the improvement relative to matrix-UCB is very marginal ... the paper is incremental.

A4: Several differences in the original deterministic games were small. To see whether the gaps grow with more play, we extended the four noisy best-response experiments from 640,000 to 2.56 million rounds. Both methods used the same matrices and the same eight random seeds. The table gives final cumulative regret as mean ± sample standard deviation. Lower is better.

GameIC-RFMatrix-UCB
RPS18.08 ± 1.8631.26 ± 0.59
Blotto15.78 ± 1.1923.88 ± 0.96
Goofspiel15.42 ± 3.3814.76 ± 3.59
Kuhn poker76.30 ± 14.1776.30 ± 14.17

On noisy rock–paper–scissors (RPS) and Blotto, IC-RF's cumulative regret grew more slowly after local updates began. Its mean advantage grew from 4.35 to 13.18 on RPS and from 2.61 to 8.10 on Blotto. On Goofspiel, the two methods had similar mean regret, with 15.42±3.3815.42\pm3.38 for IC-RF and 14.76±3.5914.76\pm3.59 for Matrix-UCB (mean ± sample standard deviation). On Kuhn, all eight runs stayed in the initial Matrix-UCB stage, which explains the identical results. These results suggest that IC-RF may offer practical benefits in games involving prolonged repeated interaction, where the learner can gradually accumulate sufficient payoff observations. We added the longer-horizon findings to Section 5.2 and the values and curves to Table 4 and Figure 4 in Appendix A.3.

Q5

What are the obstacles in extending the result beyond the assumption of having a unique, fully mixed equilibrium?

A5: One obstacle is that a missing column may offer no extra payoff. If two columns are identical, for example, deleting either one leaves the row player's guaranteed value unchanged. In our proof that increase in value helps pay for exploration. A second obstacle arises when an equilibrium assigns zero probability to a row. A learner playing close to that equilibrium can go a long time without observing the row, even if its payoff against a newly revealed column matters. With multiple equilibria, a small change in the estimated payoffs can also change which equilibrium is selected.

An extension would need a way to decide which actions still need observations and to bound the loss if an action set aside too early later becomes relevant. Section 4.4 explains where the current proof uses full support and uniqueness. The limitations paragraph in the conclusion identifies learning the equilibrium support as an open problem.

Q6

Some of the experiments are conducted on extensive-form games. ... Can the authors comment on how their approach can be applied to the extensive form?

A6: In Kuhn poker, a row in our experiment represents a complete poker policy. It specifies how that player acts given its card and the betting history. A column represents a policy for the other player. We fix three policies per player and use the payoff from playing one against another to define a 3×33\times3 matrix. Each learning round, IC-RF announces a distribution over its three rows, observes the opponent's selected column and one payoff, and updates for the next round. All baselines face the same rows, columns, and feedback rules.

The guarantee therefore concerns the value attainable by mixing over these selected policies. Learning how to bet or fold directly from hands would require updates at individual poker decision points. Blotto and Goofspiel use the same policy-matrix construction as Kuhn. In RPS the rows and columns are the three ordinary game actions. We clarified what an action represents in Section 5.1 and how the OpenSpiel policy matrices are constructed in Appendix A.2.

I thank the authors for their response. In the revision, basically half of the main body is different from the version that was initially submitted. I don't believe this major restructuring in writing is appropriate for a revision. The authors should do their best to submit a paper that effectively communicates the key ideas and motivation. In any event, even with the revised writing, I don't believe the paper's writing quality meets the bar for acceptance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.