acceptodds
Under review as a conference paper at ICLR 2027

Solving Stochastic Minimax Bandit Games

Abstract

Minimax regret is the smallest worst-case regret achievable by an online learning algorithm. At a fixed horizon, this objective provides a computational route to algorithm design: optimizing the complete history-dependent policy offline. The resulting optimization has a natural two-player zero-sum structure, with the learner minimizing regret and the environment choosing hidden reward parameters to maximize it. We develop an approximate policy-space solver for these stochastic minimax bandit games. Each iteration plans a learner response to an environment mixture, evaluates the complete policy, and updates both players' mixtures. Grid interpolation and point-based value iteration represent finite-horizon costs in sufficient statistics. Shared two-arm costs avoid a joint state grid, while policy evaluation and mixture selection retain the original multi-arm objective. The resulting policy mixture defines an online learning algorithm that adapts its actions to observed rewards. In four exactly evaluable three-arm games, complete iterations reduce strategy-pair gaps from 0.115–0.349 to 0.001–0.016. Larger-horizon experiments cover 60 settings and track regret against tuned references over training time. Independent evaluation quantifies uncertainty in their regret differences. Response controls distinguish belief resolution from pair-prior capacity; complete runs confirm that larger priors improve regret in one Beta setting. The resulting framework uses offline game solving to design adaptive online exploration policies.

Primary area:
reinforcement learning
Keywords:
Minimax Bandit, Game Thoery, Game Solving

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_MNx4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper computes finite-horizon stochastic-bandit policies through a zero-sum game between a history-dependent learner and an environment distribution. A policy population is expanded by approximately responding to the current environment mixture, evaluating each complete policy, and solving the resulting restricted game.

The main computational contribution is a shared two-arm planner, implemented through grid interpolation or point-based value iteration. Pairwise action-cost differences are aggregated into a multi-arm policy, avoiding a joint planning grid. Experiments combine exact small-game evaluation, a 60-setting development benchmark, independent frozen-policy comparisons, and controls for prior compression and response capacity.

Critical strengths

1. The small-game validation is convincing. Figure 3 and Table 7 evaluate complete solver iterations using exact finite-state expectations and an unrestricted joint best response. Pairwise policies finish within 0.35% of the joint solver’s worst regret across the four tested games. This directly demonstrates that the approximation can preserve near-optimal performance in these settings.

2. The mathematical distinctions are handled carefully. The manuscript correctly separates finite-support minimax guarantees, empirical regret estimates, and feasible-response diagnostics. In particular, it acknowledges that Equation (32) provides a lower bound on the Nash gap rather than a certificate of near-equilibrium. I found no obvious error in the fixed-prior regret identity, stated sufficient statistics, symmetry argument, or least-squares aggregation derivation.

3. The experimental controls reveal useful mechanisms. The distinction between belief resolution and prior-support capacity is informative. Tables 16–20 show that increasing belief capacity cannot necessarily repair information lost through prior compression. The independent evaluations, stronger RL comparators, and reporting of unfavorable results improve the credibility of the study.

Critical weaknesses

**1. The independent evaluations provide substantially weaker support for performance gains than the development benchmark. **

The 52/60 and 56/60 favorable comparisons use settings involved in configuration selection. Moreover, their ordered-arm evaluation differs from the common root-relabelling protocol used in the independent studies.

In Table 1, none of the favorable differences excludes zero under the approximate simultaneous intervals. Beta PBVI is worse than the strongest reference by 0.578 [0.225, 0.931]. All twelve corresponding intervals in the six additional settings also include zero (Table 11). On the structured Beta stress set, PBVI’s regret is 6.348 versus 3.192 for the strongest reference (Tables 12–13).

These results do not establish that the methods are equivalent, and the paper appropriately qualifies them. However, they leave the larger-scale performance advantage unresolved. This matters because improved finite-horizon policies are a central motivation for the additional computation.

2. The reliability of the central pairwise approximation remains insufficiently characterized.

Equation (13) establishes that the arm scores fit pairwise differences in least squares. It does not establish that their minimizing arm approximately solves the original multi-arm decision problem. The approximation omits other-arm evidence and alternative future sampling opportunities, and its global versus pair-local clock changes the planning problem.

The exact controls provide positive evidence, but cover short three-arm Bernoulli games. At larger horizons, the results demonstrate substantial sensitivity to prior compression. Full priors substantially improve Beta performance, yet one full-prior adaptive run still has Sobol-set regret 4.183 versus 3.183 for the reference. Uniform response targets also give lower transfer-set point regret than adaptive targets for every full-prior seed, although adaptive training is cheaper.

A universal approximation theorem is not necessary. What remains unclear is when this representation offers a dependable accuracy–computation tradeoff, and how its capacity should be chosen before observing setting-specific performance.

3. The incremental contribution over existing computational minimax methods needs stronger substantiation.

Existing work (https://arxiv.org/pdf/2302.10831) already formulate policy–prior optimization and develop both gradient-based and Bayes-oracle methods. Adusumilli already computes numerical Bayes and minimax bandit policies through limiting control problems. The submission acknowledges these connections correctly.

I therefore view the new contribution primarily as the finite-horizon response implementation and shared pairwise construction. Those are potentially valuable, but the current evidence does not fully establish their broader advantage. The RL comparison evaluates one adapted gradient-based route, while the strongest exact validation remains small. A sharper account of the capability gained over earlier numerical approaches would strengthen the significance argument.

Questions for authors
  1. For one of the strongest favorable frozen-policy results, can a more precise independent evaluation resolve whether the improvement is practically meaningful? Please keep the policy, reference set, and evaluation protocol fixed.

  2. For existing, unchanged policy checkpoints, how much of the development-to-frozen performance difference comes from arm relabelling versus fresh rollout noise? This would help interpret Figure 4.

  3. What practical criterion should determine pair-prior capacity and clock convention? Can the existing controls identify a diagnostic that warns when compression materially damages response quality?

  4. What is the most important capability enabled by this approach beyond the cited Bayes-oracle and numerical-control methods: larger arm counts, finite-horizon accuracy, computational savings, or another property? Which existing result most directly establishes it?

2 comments

Thank you for your careful assessment of the method and experiments.

Main response: Finite-horizon multi-arm solving

Matching minimax regret rates establishes the order of growth. Our empirical question concerns the numerical solution at fixed arm count and horizon: what complete adaptive policy can offline game solving compute, and how much regret improvement does its computational budget buy? The target is an equilibrium learner attaining the specified game's minimax value.

The response to each environment mixture must value both reward and future information. Joint planning tracks all arms' evidence; sufficient statistics and shared arm updates allow a reusable two-arm Grid/PBVI calculation. Aggregated costs produce multi-arm actions, and complete-policy regret determines mixture selection.

Exact small games measure solution gaps and matched solver cost. Larger experiments measure achieved regret, while capacity controls show where additional computation helps. The completed precision and coverage evaluations test the resulting policies.

Does higher-precision evaluation resolve the gains?

Yes. The unchanged Gaussian PBVI deployment gives the clearest resolved gain after the fixed-budget 16× evaluation. At K=3,T=100:

PolicyReduction versus strongest referenceApprox. simultaneous 95% difference intervalHoeffding simultaneous 95% difference interval
Gaussian PBVI7.25%[−1.080, −0.586][−1.496, −0.170]

Both intervals concern our worst regret minus the strongest reference's worst regret. Policies, mixture weights, environments, root assignments and references stayed fixed. The gain remains favorable under both analyses, so this comparison resolves a finite-horizon improvement at the measured magnitude. The General response reports all six Table 1 comparisons, including the unresolved and unfavorable outcomes.

Do labels or fresh samples explain the change?

The shared pairwise construction gives permutation-equivariant action probabilities under symmetric tie-breaking (Appendix B.7). For the verified frozen Beta PBVI mixture, relabelling arms therefore preserves expected regret.

With this policy, its weights, 58 environments and original labels fixed, replacing the original sampling stream changes estimated worst regret from 3.170 to 3.955. Both evaluations use 256 trajectories per environment/component. This change occurs with unchanged labels and fresh sampling after the original stream was used for mixture selection. The larger Table 1 evaluation improves precision for the frozen-policy comparisons.

How was response capacity selected?

Capacity and clock were selected jointly by complete K-arm development regret, with fixed parameters and an empty pool per run. Pair-prior capacity retains two-arm parameter atoms; belief capacity sets design-posterior rows.

The controls give an actionable diagnostic: fix q and the full environment support, then compare increasing prior capacity with increasing belief resolution. A large gain from prior capacity with little recovery from more beliefs indicates that discarded parameter distinctions matter. In Beta, these changes give response regret 2.234 and 3.260 respectively, from 3.331; construction CPU is 1.15× and 12.46×. This observed contrast identifies a productive allocation of computation. The diagnostic comes from the controls; reported configurations were selected by the complete-policy criterion above.

Does larger prior capacity improve complete runs?

The original Beta stress result is unfavorable: 6.348 versus the strongest reference's 3.192. Full-versus-compressed pair-prior controls use the same training support and independent design/stress/Sobol evaluations. Across three seeds, design regret falls from 4.110–4.266 to 2.974–3.063 (MOSS: 3.353). All nine approximate simultaneous full-minus-compressed intervals across seeds and sets are below zero; design comparisons with MOSS include zero. These are complete-solver capacity gains, complementing the fixed-q response-level diagnostic.

Why use different clocks?

Embedding a two-arm planner in a K-arm policy requires specifying which time layer to query. Global timing uses T−t remaining pulls; pair-local uses T−N_i−N_j, retaining ordinary two-arm timing. Here t counts all elapsed pulls and N_i,N_j the queried arms' pulls; deployment always stops at T.

Clock was selected jointly with other parameters by complete-policy development regret. Table 25 records global for selected multi-arm Gaussian/Bernoulli PBVI configurations and pair-local for Beta Grid. The reported comparisons evaluate jointly selected complete configurations.

Why use adaptive response targets?

Adaptive responses target the current restricted-game q; uniform responses weight design environments equally. Both use minimax masters for final mixtures. Under compressed capacity, adaptive has lower design-set point regret in all nine family–seed pairs (Table 15/C.9).

With full Beta pair priors, uniform has lower additional-set point regret for every seed. Adaptive costs 378–402 versus uniform's 2,422–2,594 CPU seconds for six responses each (C.11); one adaptive run has Sobol regret 4.183 versus the reference's 3.183. Capacity and evaluation domain affect the tradeoff.

What capability does the solver add?

Most important added capability

Repeated finite-horizon multi-arm response planning with a shared, budget-controlled representation. At fixed horizon, prior size and numerical resolution, increasing K adds pair queries without adding state coordinates to the shared planner. Complete-policy evaluation keeps the resulting population search tied to original multi-arm regret.

Most direct evidence

Figure 3/Table 7 isolates the quality of this construction against joint planning. Across four exactly evaluable three-arm games, final pairwise-solver gaps are 0.001–0.016 and worst regret is within 0.35% of the joint solver, with 2%–40% lower solver CPU in matched complete runs (Table 8). Figure 4 supplies complementary scale evidence up to eight arms and T=1,000; Figure 5 measures regret improvement against training time. Together these test the accuracy and computational reach of shared responses.

Connection to earlier solution routes

"Minimax-Bayes Reinforcement Learning" (Kleine Buening et al., 2023) provides gradient and Bayes-oracle methods; we supply a bandit-specific numerical response mechanism. "Risk and Optimal Policies in Bandit Experiments" (Adusumilli, 2025) derives numerical policies through local-asymptotic control problems; our response/population calculation uses the represented discrete-horizon game's payoffs. The General response gives the fuller method comparison and the evaluation of the implemented gradient method from "Minimax-Bayes Reinforcement Learning".

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

This paper considers the minimax regret problem for stochastic bandits with a fixed horizon T. The authors formulate it as a two-player zero-sum game, where the learner picks a history-dependent policy and the environment picks a distribution over the reward parameters. Then they solve this game approximately by a PSRO-style loop. In each iteration, they solve the restricted game on a finite set of environments, compute a Bayesian response to the current environment mixture, evaluate the new policy in the original K-arm game, and add it to the policy pool. The response is computed by a two-arm planner (grid interpolation or PBVI) in the space of sufficient statistics, and the multi-arm policy is obtained by combining pairwise cost differences. The method is evaluated on small games where the exact game value can be computed, and on a benchmark of bandit settings against standard baselines.

Critical strengths

Using offline game solving to design an online exploration policy is a reasonable direction, and the paper explains its relation to Buening et al. 2023 and Adusumilli 2025 clearly. The small-game study in Section 5.1 is a good sanity check: on games where the exact value can be computed, the pairwise response is very close to the joint planner in worst regret, and the strategy-pair gaps become small after a moderate number of response calls.

Critical weaknesses

First, the novelty is limited. Every component of the method already exists. The formulation of minimax regret as a zero-sum game between the policy and the prior is the formulation of Buening et al. 2023, which the paper also cites as the closest work. It is also a well-known result in decision theory that the minimax policy is the Bayesian policy under the least favorable prior. The solver is PSRO / double oracle (McMahan et al. 2003, Lanctot et al. 2017). The response planners are grid interpolation in sufficient statistics (Zhu et al. 2023) and PBVI (Pineau et al. 2003). What is new is the way these parts are put together: keeping the finite horizon, using a policy population instead of a single policy, sharing one two-arm response across arm pairs, and the exact-gap evaluation on small games. This is an engineering contribution, and the introduction should state this directly instead of presenting the game formulation as the contribution.

Second, the paper has no theoretical result. There is no regret guarantee for the deployed policy, no approximation guarantee for the pairwise decomposition, and no convergence statement for the PSRO loop. The only quantitative evidence on solution quality is for K=3 and T≤20.

Third, the independent evaluations do not show a real improvement. In Table 1, all three Hoeffding intervals contain zero. The approximate intervals for Gaussian and Bernoulli contain zero, and for Beta the PBVI interval favors MOSS (+0.578, [0.225, 0.931]). In Table 11, all twelve intervals contain zero. In the structured stress set (Table 13), Beta PBVI is worse than the best baseline by 3.16 with an interval that excludes zero. So a more accurate conclusion is that the method is comparable to tuned MOSS or UCB-V and sometimes worse, not that it improves on them.

Questions for authors
  1. The game is solved on a finite set of 50 to 64 representative environments, and Appendix B.9 says that U_M is only an upper bound for this finite-set game, not for the continuous domain. Table 13 shows the Beta PBVI policy becomes much worse once the environments are outside the design set. So when does this finite-support approximation break? How were the representative environments chosen so that they cover the hardest instances (Appendix C.13 mentions high-regret screening only for Gaussian), and is there any control on the regret of the learned policy outside the support?

  2. MOSS is already minimax optimal up to constants, so the room for improvement is only in the constant. From Table 4 and Table 27, at Bernoulli K=2, T=20 the exact Bayes value is 1.238, MOSS is 1.388, and Grid is 1.326, so the gap between MOSS and the minimax value is about 11% and the method captures about one third of it. What is this gap at K=3, T=100? If it is of the same order as the evaluation noise, the frozen evaluation cannot resolve a difference no matter how many episodes are used.

  3. Section 1 states that the coupled prior prevents the Gittins-style decomposition, while Section 4.4 states that each pair ignores the other arms' evidence and future sampling, and Appendix B.7 makes no optimality claim for the full-K problem. Under what condition on the prior is the pairwise aggregation in Eq. (8) equal to the true K-arm Bayes response?

2 comments

Thank you for your detailed review and assessment of the small-game validation.

Main response: bandit-specific computation

Our main contribution is a bandit-specific response construction for finite-horizon game solving, with experiments quantifying the resulting solution quality and computational cost. Matching regret rates determines the order of growth; the numerical minimax value and an equilibrium policy at fixed arm count and horizon require further analysis or computation. Our empirical study targets this numerical policy gap through offline game solving. A generic population loop still needs an affordable response to each environment mixture; joint bandit planning tracks every arm's evidence.

What the construction adds

We derive one shared two-arm planning model from the current environment mixture, query cost differences for every pair, and aggregate them into multi-arm decisions. Complete-policy regret supplies the payoff row used to select both players' mixtures. At fixed horizon, prior size and numerical resolution, the response representation avoids adding state coordinates as K grows. Exact joint comparisons test the solution quality retained by this approximation, and training curves measure its computational benefit.

Relation to the closest solver

"Minimax-Bayes Reinforcement Learning" (Kleine Buening et al., 2023) already formulates policy–prior games and develops gradient and Bayes-oracle methods. Our construction supplies a numerical response for finite-horizon bandits with coupled priors. We implement that paper's gradient-based approach for the same finite-horizon tasks. Grid/PBVI have lower point-estimated worst regret than every evaluated neural policy trained for 1,024 updates in the three K=3,T=100 tasks (Appendix C.6). The new precision evaluation also resolves Gaussian Grid/PBVI and Bernoulli PBVI improvements over their strongest tested references under approximate simultaneous intervals. The General response details the individual numerical-method connections.

How are environments selected?

The relevant coverage risk is an omitted environment on which the learned policy has higher regret. The represented environments support game optimization; additional and searched instances test whether the learned policy remains effective beyond them.

At K=3,T=100, Gaussian uses 64 environments from high-regret screening and geometrically separated points. Bernoulli/Beta use 50/58: structured instances, supplied prior support, accumulated search support and proposals, deduplicated under arm permutations (revised Appendix C.13). Each iteration optimizes the environment weights over this support.

Appendix B.9 provides bounds for the represented finite game. Off-support performance is assessed through the expanded evaluations below. Pair-prior compression is a separate response approximation: its controls keep the full multi-arm environment support fixed.

Why does Beta PBVI struggle?

On the original Beta stress set beyond the design support, PBVI's worst regret is 6.348 versus 3.192 for the strongest reference. Same-support capacity controls (Table 18) identify information loss as one contributing factor. Across three paired seeds, retaining the full pair prior reduces design-set regret from 4.110–4.266 to 2.974–3.063. All nine design/stress/Sobol full-minus-compressed approximate simultaneous intervals lie below zero; the design-set comparisons with MOSS include zero. These are separate control runs; the original frozen policy is unchanged.

Does performance extend beyond the design set?

The unchanged five-component Gaussian PBVI mixture (K=3, T=100) retains an advantage on the tested 364-environment union in the same parameter domain: original 64, structured stress 164, new Sobol 128 and searched high-regret candidates 8.

Search combines boundary/near-tie proposals with Sobol and uniform samples, ranks them by this frozen policy's regret, then locally refines high-scoring candidates twice. All eight selected candidates enter independent final evaluation (Appendix C.19).

SetPBVI worst regretBest referenceDifference [95% interval]
Original 6410.70311.636 (MOSS)−0.932 [−1.250, −0.614]
Union 36410.99311.744 (KL-UCB++)−0.751 [−1.149, −0.496]

References are fixed KL-UCB++, MOSS and UCB-V deployments. Difference is PBVI's whole-set maximum minus the lowest reference whole-set maximum; union reduction is 6.39%. Evaluation uses 3,072 contributions per environment/component, all six arm assignments and fixed mixture weights. The 1,000 paired, assignment-stratified bootstrap replicates recompute maxima and the reference minimum. Intervals are approximate pointwise 95%, conditional on frozen deployments and finite test sets (Appendix C.19, Tables 28–29).

How close are the policies to optimality?

At K=3,T=100, the MOSS-to-minimax gap remains uncomputed. We therefore evaluate two questions separately: exact small games measure distance to the minimax value; independent rollouts measure whether a fixed learned policy improves on a reference at larger horizons.

For Bernoulli K=2,T=20, Table 4's 1.237798 is an exact Bayes lower bound for one environment mixture. Grid's exact worst regret is 1.326424, bounding its excess over the finite-game optimum by 0.088626. Table 27's MOSS value comes from a separate development Monte Carlo comparison. The bracket quantifies Grid's possible excess regret; identifying the fraction of MOSS's optimality gap closed additionally requires the minimax value.

Why is exact joint planning expensive?

At K=3, T=100, the Bernoulli full lattice has 1,609,344,100 nonterminal success/failure-count states and about 4.83 billion state–action backups, before posterior/expectation costs. Sparse methods may visit fewer states; Gaussian/Beta also require continuous reward integration. This motivates compact responses and small-scale exact validation.

Can more evaluation resolve the difference?

A nonzero fixed-policy regret difference can be resolved by increasing independent evaluation samples. The completed 16× evaluation demonstrates this on the reviewer's Bernoulli K=3,T=100 case: PBVI improves on MOSS under the approximate simultaneous interval, while Grid remains unresolved. The full differences and intervals are in the General response's Table 1 update.

Gaussian Grid/PBVI also improve under that analysis; Gaussian PBVI improves under Hoeffding as well. Beta PBVI remains worse. More precise policy comparison reduces sampling uncertainty while the exact optimum remains a separate planning calculation.

Table 11 currently gives favorable point estimates in 5/6 PBVI and 3/6 Grid settings, with all 12 intervals including zero. Its fixed-policy precision extension is planned for follow-up.

When are pairwise responses exact?

For K>2, we have not established a prior condition under which Eq. (8) equals the exact joint Bayes response. We use it as an approximate response. The structural basis is that every arm follows the same pull–observe–update mechanism, allowing reuse of one planner. The approximation omits other arms' evidence and future sampling opportunities within each pair.

We test the consequence at the game-solution level. Four exact three-arm games compare complete runs with uncompressed pairwise and joint planners. Unrestricted joint responses provide the lower bounds needed to measure the pairwise solver's strategy-pair gap. Final gaps are 0.001–0.016, and mixture worst regret is within 0.35% of the joint solver (Figure 3/Table 7). Thus the empirical claim is a compact response with small measured solution error in these controlled games.

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

The paper considers the classical bandit problem from a two-player game perspective. Particularly, the learner is a player in a policy space, and the environment is one in the parameter space. They form a minimax game. The paper proposes a value iteration based method as well as an offline solver specifically designed for the game on the learner side. The paper empirically validates the proposed method by conducing experiment with Gaussian, Bernoulli, and Beta families, and compare the method with the existing common bandit methods. In many cases, the algorithm is reported to outperform the SOTA methods.

Critical strengths

The paper's perspective of solving the bandit problem through a minimax game between a learner in a policy space and an environment in the parameter space of the problem instance is interesting. With the new perspective, the paper proposes a value iteration based method to solve the game, as a new route.

Critical weaknesses
  1. The reviewer has a hard time reading the paper. This difficulty comes from two aspects. On the one hand, the contribution compared to the existing literature is unclear, as the paper presents what they do (also sometimes what they do differently), but not what is the position of these findings in the literature or what new knowledge we would gain by doing differently. It is also unclear to the reviewer what is the advantage of solving the problem in this new perspective, compared to the existing methods. On the other hand, the subjective part is that the paper is written with a list of what has been done and what is the result. The insight/knowledge/enthusiasm, however, behind the findings seems to be hidden. Maybe a bit overly subjective, but from a reader's perspective, it has been a bit hard and sad for the reviewer to convince themselves the contributions and significance of the work.

  2. The experiment results seem to have cases where the proposed method does not outperform the SOTA methods. While Figure 4 is informative in the sense of including all the results, there has been a lack of investigations into these edge cases. Hence, the validity is not fully supported in its current form.

Questions for authors
  1. What is the computational complexity of the proposed method, both in theory and in the numerical experiments? Would it be better than the existing bandit methods?

  2. Is there any insight on the theoretical guarantee of the proposed method? Bandit methods typically enjoy good guarantees which also make them appealing.

  3. The method seems to be quite complicated, though maybe only to the reviewer, and thus it is unclear to the reviewer what is the advantage of this method. Bandit methods are typically relatively easy to interpret and implement.

  4. What is the novelty of the method, compared to the existing planning methods in two-player games?

  5. Is there any reasoning or justification for the edge cases where the proposed method is not outperforming?

3 comments

Thank you for your careful reading and detailed comments.

Main message: Finite-horizon policy design

For rewards in [0,1] and 2 ≤ K ≤ T, the minimax lower bound and MOSS upper bound both scale as √(KT) (Audibert and Bubeck, 2009, "Minimax Policies for Adversarial and Stochastic Bandits"). K is the arm count and T the horizon. Matching these rates settles the growth order. Algorithms can still have different constants and finite-horizon regret, and the rate result leaves the numerical minimax value and a policy attaining it undetermined.

Our empirical objective is to compute better complete exploration policies at the specified K,T. Game solving supplies a numerical target: the learner's worst regret and the environment mixture's best-response lower value should approach the same game value. The learner's strategy is a complete online algorithm; the opponent chooses hidden reward parameters. We generate responses, evaluate complete policies and update mixtures. The resulting algorithm continues to adapt to rewards online.

Response computation is the bottleneck. Sufficient statistics summarize histories, but joint planning still tracks all arms' evidence. Shared arm updates allow reusable two-arm Grid/PBVI costs to guide multi-arm decisions. Small exact games measure the numerical solution gap; larger experiments measure regret and cost at practical budgets.

What is the computational cost?

Game solving computes a reusable policy offline. Its practical value is the regret improvement obtained for this computation; Figure 5 measures that tradeoff. Let m be retained prior atoms, P design-belief rows, V maximum vectors per layer, J observation nodes per atom/action, and G Grid nodes per layer. PBVI uses O(TmV) storage, O(TPJm²V) dense-backup time (plus belief generation/selection), and O(K²mV) per online decision. Grid uses O(TG) storage and O(K²) pair queries per decision. Training also evaluates complete policies and solves restricted-game linear programs.

At K=3,T=100, Figure 5 training takes 1.2/0.8/32.8 wall-clock minutes for Gaussian/Bernoulli/Beta Grid and 5.2–10.0 for PBVI. A separate deployment study reports Grid/PBVI/MOSS costs of 5.06/8.20/0.14 (Gaussian), 7.87/11.22/0.09 (Bernoulli), and 45.83/13.20/3.49 (Beta): component-weighted batched-rollout CPU seconds per million decisions, including feedback generation. These measurements quantify the additional computation used to improve finite-horizon regret. Saved policies amortize training over repeated episodes; deployment retains the measured online cost.

What guarantees can we provide?

Our empirical objective is to reduce the numerical gap to the finite-horizon minimax value. The exact-game study measures this target directly.

For M represented environments, U_M(σ) is learner mixture σ's maximum expected regret; L_M(q) is the minimum regret weighted by environment mixture q over all history-dependent randomized policies. Both average hidden arm assignments. They bracket the same finite-game minimax value. Thus g_M=U_M−L_M is the strategy-pair Nash gap and bounds the learner's excess worst regret; zero identifies equilibrium in that game.

Figure 3 uses uncompressed complete-state pairwise responses, exact mixture evaluation for U_M, and separate unrestricted joint responses for L_M. Across four short three-arm Bernoulli games, pairwise-solver gaps fall from 0.115–0.349 after the first response to 0.001–0.016 after 24; final worst regret is within 0.35% of the joint-solver mixture. Larger-horizon results evaluate numerical approximations empirically through policy regret and cost.

Why spend computation offline?

Practical benefit

The offline computation searches over complete exploration policies, including how an action's information changes later decisions. This gives a direct way to improve actual regret at the intended horizon. The completed precision evaluation supports gains for Gaussian Grid/PBVI and Bernoulli PBVI; the unchanged Gaussian policy also retains an advantage over all three tested classical references on the expanded environment set (General response).

What deployment requires

Each episode samples one saved policy component. Observed rewards update sufficient statistics; stored Grid/PBVI values produce pair costs and the next arm. The online code performs these queries while the training cost is amortized over episodes sharing the reward family, K and T.

What is new relative to existing two-player game solvers?

Existing game-solving framework

Double oracle in "Planning in the Presence of Cost Functions Controlled by an Adversary" (McMahan et al., 2003) and PSRO in "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning" (Lanctot et al., 2017) expand strategy sets through responses to opponent mixtures. We use this population framework and design its response computation for bandits. Here, the environment chooses hidden reward parameters at the start; a learner response must allocate a finite sampling budget adaptively from observed rewards.

Bandit-specific response construction

Under fixed environment weights, the known reward likelihood specifies both immediate rewards and evidence updates. Sufficient statistics compress histories. The common pull–observe–update structure then allows one two-arm planning model to serve all pairs: Grid/PBVI supplies cost differences, and antisymmetrization and symmetric aggregation convert them into multi-arm actions. At fixed horizon, prior size and numerical resolution, the shared representation gains no state coordinates as K grows; each decision uses O(K²) pair queries.

This produces an approximate complete response. Its payoff is measured in the original K-arm game, and that payoff row determines subsequent mixture updates. The contribution is this task-specific response construction inside the game-solving loop.

Evidence of game-solving progress

Four exact three-arm games compare complete runs with pairwise and joint responses. After 24 response calls, pairwise-solver strategy-pair gaps reach 0.001–0.016 and worst regret is within 0.35% of the joint solver, with 2%–40% lower solver CPU in these matched complete runs (Figure 3, Tables 7–8). Figures 4–5 then measure the attainable scale and regret improvement per computation budget.

Why do some settings perform worse?

Matching regret rates answers the growth-order question. Our game-solving objective is the numerical finite-horizon value: an equilibrium learner minimizes worst regret over all policies in the same game. Every baseline is feasible there. Once the computed policy's optimality error is smaller than a baseline's gap to this value, it achieves lower worst regret.

A finite-budget policy that still trails a baseline has a remaining optimality gap to close. We study empirically how response accuracy, retained information and policy search affect that gap. The exact small-game bounds measure it directly; larger runs evaluate the policies obtained with practical computational budgets.

The Beta control provides a concrete mechanism. Retaining more pair-prior information reduces complete-policy regret across separately trained runs on the same environment support (Table 18). This identifies a response-representation error that can be reduced through additional capacity. The benefit appears in the complete solver, making prior capacity a productive place to spend additional computation.

Thank you for the detailed response. I get the idea of the method now. I have to maintain my score, as the writing does not seem to be easily addressed and the advantage of the methods is not convincingly demonstrated. I hope the authors could understand.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response

We thank all three reviewers for their careful reading and constructive feedback.

Our goal is empirical game solving: closing the numerical gap between upper and lower bounds on finite-horizon minimax regret.

For rewards in [0,1] and 2 ≤ K ≤ T, MOSS's O(√(KT)) upper bound matches the Ω(√(KT)) minimax lower bound (Audibert and Bubeck, 2009, "Minimax Policies for Adversarial and Stochastic Bandits"). K is the arm count and T the horizon. Matching rates settle the order of growth; they leave the numerical minimax value and an equilibrium policy at fixed K,T undetermined.

The learner chooses a complete adaptive online algorithm; the environment chooses hidden reward parameters or their distribution. Expected cumulative pseudo-regret is the environment's payoff and the learner's cost. An equilibrium learner attains the game's minimax value, no greater than any baseline's worst regret in that game. We search through approximate responses and policy populations. Exact small-game upper/lower brackets measure progress toward equilibrium; larger experiments measure achieved regret and computational cost.

From bandit structure to a computable response

Fixing environment weights q gives a Bayesian response problem: pulls earn reward and reveal information. Sufficient statistics summarize histories; abstraction controls planning cost through a smaller representation (Brown and Sandholm, 2018, "Superhuman AI for Heads-up No-limit Poker: Libratus Beats Top Professionals").

We induce a shared two-arm model from q and aggregate Grid/PBVI cost differences into multi-arm actions. At fixed horizon, retained-prior size and resolution, larger K adds O(K²) pair queries without adding state coordinates. Complete policies are evaluated in the original K-arm game; their payoff rows determine both players' mixtures. Environment weights range over the fixed support. Section 4 and the appendices specify the numerical models and clocks.

How the computational problems differ

PSRO: organizing search and computing a response

PSRO in "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning" (Lanctot et al., 2017) organizes policy populations, payoff evaluation and mixture updates. Its application still needs a response oracle. We specify this costly step: convert the environment mixture into a shared two-arm planning problem and turn its cost differences into a complete multi-arm response.

Zhu et al.: limiting control and discrete-horizon responses

In "Continuous-in-time Limit for Bayesian Bandits" (Zhu et al., 2023), the authors compute an approximately Bayes-optimal policy for a supplied prior by solving a limiting HJB in normalized count/reward coordinates. Our Grid stores costs at each discrete horizon layer for responses to changing environment mixtures. Shared pair queries replace a joint multi-arm value surface, so the grid describes a reusable response component whose resulting policy is evaluated in the original game.

PBVI: selecting plans and reducing the response model

"Point-based Value Iteration: An Anytime Algorithm for POMDPs" (Pineau et al., 2003) selects reachable beliefs and conditional-value plans for a supplied POMDP. Applied to the full bandit model, it still plans over joint reward hypotheses. We instead construct a two-arm model from the current environment mixture: retained parameter pairs index conditional costs, and queried cost differences guide every arm pair. Sharing this smaller response model complements PBVI's selection of plans within that model.

Minimax-Bayes RL: implementing the response oracle

"Minimax-Bayes Reinforcement Learning" (Kleine Buening et al., 2023) studies the same policy–prior game through gradient updates and Bayes-oracle cutting planes. Their experiments include finite-horizon MDPs and discounted bandits with Gittins responses. Our coupled priors and shared finite sampling budget require a different bandit response from the independent-arm discounted Gittins decomposition. We supply it through shared numerical planning. Relative to their gradient route, the computational distinction is explicit reward/information backups versus learning policy parameters from sampled gradients.

Adusumilli: asymptotic risk and finite-game policy search

"Risk and Optimal Policies in Bandit Experiments" (Adusumilli, 2025) studies local-asymptotic Bayes/minimax risk using diffusion-limit PDEs and derives numerical policies. Our solver generates responses for the discrete-horizon game and selects mixtures using complete-policy regret at that horizon. The shared pairwise response architecture makes these repeated calculations practical; exact small-game gaps and computation–regret curves assess the resulting finite-game solutions.

Implementation of the published gradient method

We implement the gradient-based approach in "Minimax-Bayes Reinforcement Learning" (Kleine Buening et al., 2023) for finite-horizon bandits. The arm-equivariant neural policy uses public statistics and sampled-regret gradients. At 1,024 updates per run, Grid/PBVI have lower point regret than every evaluated deployment across the prescribed seeds and exploration choices in all three K=3,T=100 tasks (Appendix C.6).

Main evidence

Four exact three-arm games reduce strategy-pair gaps from 0.115–0.349 to 0.001–0.016. In the matched complete runs, pairwise worst regret is within 0.35% of joint planning while solver CPU is 2%–40% lower (Figure 3, Tables 7–8).

Figure 4 covers 60 settings up to eight arms and T=1,000; Grid/PBVI have lower selected point regret than the strongest benchmark reference in 52/60 and 56/60 settings. Figure 5 tracks regret versus training time. Figure 4 uses development selection and its stated arm-ordering protocol; the frozen comparisons below use independent samples and common root relabellings.

New results: Table 1 precision evaluation

We completed a 16-fold larger evaluation at K=3, T=100: 98,304 rollout contributions per environment/component, covering 57 frozen deployments and 3,224 method–environment means. Policies, weights, environments, root assignments and references stayed fixed. Gaussian Grid uses the documented regenerated tables.

Differences are our worst regret minus the best reference's worst regret; negative values favor our policy. Relative change divides this difference by the best-reference point regret.

PolicyRegret differenceRelative changeApprox. simultaneous 95% intervalHoeffding simultaneous 95% interval
Gaussian Grid−0.554−4.82%[−0.830, −0.278][−1.161, 0.101]
Gaussian PBVI−0.833−7.25%[−1.080, −0.586][−1.496, −0.170]
Bernoulli Grid−0.066−1.20%[−0.190, 0.058][−0.334, 0.202]
Bernoulli PBVI−0.195−3.54%[−0.316, −0.074][−0.463, 0.073]
Beta Grid+0.085+2.58%[−0.006, 0.178][−0.098, 0.306]
Beta PBVI+0.432+13.15%[0.344, 0.520][0.211, 0.653]

The approximate simultaneous intervals resolve Gaussian Grid/PBVI and Bernoulli PBVI improvements; Gaussian PBVI also improves under Hoeffding. Beta PBVI has higher regret, while Bernoulli Grid and Beta Grid remain unresolved at this precision.

We retain the submitted procedure: simultaneous mean bands are propagated through environment maxima and reference minima, then opposite endpoints are subtracted. Joint coverage widens intervals; more samples tighten them. The approximate analysis uses 2,000 stratified bootstrap replicates. Table 11 precision evaluation is planned next with fixed policies and protocol.

New results: fixed-policy coverage

We evaluated the unchanged Gaussian PBVI deployment at K=3, T=100 on 364 environments in the same parameter domain: design instances, structured stress instances, new Sobol samples and searched high-regret candidates. Search ranks structured/random proposals by policy regret and locally refines high-scoring candidates. Its five components and weights stayed fixed; MOSS, UCB-V and KL-UCB++ used fixed configurations on the same sets.

Environment setCountPBVI worst regretBest of three referencesDifferenceApprox. pointwise 95% interval
Original design support6410.70311.636 (MOSS)−0.932[−1.250, −0.614]
Structured stress set16410.80311.741 (KL-UCB++)−0.938[−1.229, −0.605]
New Sobol samples12810.99311.744 (KL-UCB++)−0.751[−1.140, −0.454]
High-regret search candidates810.85111.538 (KL-UCB++)−0.686[−0.981, −0.352]
Combined set36410.99311.744 (KL-UCB++)−0.751[−1.149, −0.496]

PBVI's combined-set worst regret is 6.39% below the strongest of these three references. All four subset comparisons also favor PBVI. Each set selects its reference by whole-set worst regret, so rankings can change with the set.

Evaluation uses 3,072 contributions per environment/component across all six arm assignments. The intervals use 1,000 paired, assignment-stratified bootstrap replicates, recomputing environment maxima and the reference minimum. They are approximate pointwise intervals for the frozen policies on the evaluated finite sets.

Changes in the revised PDF

The Introduction states the empirical game-solving objective; §4.1 clarifies both players' mixture updates. Table 1 and Appendix C.6 incorporate the precision evaluation. Section 5.4 and Appendix C.19 (Tables 28–29) add the Gaussian coverage results. The appendices clarify clocks, label symmetry, per-component evaluation budgets and exact joint-planning cost.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.