acceptodds
Under review as a conference paper at ICLR 2027

Computing Equilibria in Games with Stochastic Action Sets

12 views

Abstract

The study of learning in games typically assumes that each player always has access to all of their actions. However, in many practical scenarios, players' available actions might be restricted due to exogenous stochasticity. To model this setting, for a game with action set for each player , we introduce the corresponding Game with Stochastic Action Sets (GSAS) which is parametrized by a probability distribution over the players' set of possible action subsets . In a GSAS, players' strategies and Nash equilibria (NE) admit prohibitively large representations, and existing algorithms for NE computation scale poorly. Under the assumption that action availabilities are independent between players, we show that NE in two-player zero-sum (2p0s) GSAS can be approximately represented by a compact vector of size , overcoming the naïve exponential-sized representation. Computationally, we introduce an algorithm that minimizes ranking regret, converging to NE with high probability in 2p0s-GSAS with rate for time horizon . Finally, using the iterates of our algorithm, we develop a stochastic approximation procedure to recover compactly represented NE.

Primary area:
learning theory
Keywords:
zero-sum games, stochastic action sets, equilibrium representation, equilibrium computation, no-regret learning

Reviews

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

The paper studies games where players privately receive random subsets of available actions. Under independence across players, it reduces equilibrium computation to implementable action marginals and shows that these marginals admit approximate proportional-weight representations, Additional results establish polynomial-bit approximate-equilibrium representations and a separation when availability is corrected.

CAT-FTPL achieves expected hindsight ranking regret of O(∣Ai∣Tlog⁡∣Ai∣)O(\sqrt{|A_i|T\log |A_i|}), yielding convergence of averaged marginals to Nash equilibrium in two-player zero-sum games. A stochastic approximation procedure recovers compact playable strategies, with a slower finite-time guarantee. Experiments examine convergence and compare runtime against expanded LP and Bayesian-game methods.

Critical strengths
  • Quantitative compactness and its limits. Polynomial-bit approximate equilibria provide a meaningful improvement over explicitly storing a policy for every availability subset. The correlated-availability lower bound complements this result by identifying a genuine limitation of compact representation
  • A learning guarantee suitable for adaptive self-play. The analysis controls the expected hindsight maximum over ranking policies, rather than only regret against a comparator fixed outside the expectation. Connecting this guarantee to averaged equilibrium marginals and then recovering a playable weight vector provides a useful computational framework.
Critical weaknesses
  • Several central ingredients has substantial precedents. Azrieli and Rehbeck(2026) already related positive luce weights to the relative interior of feasible marginals sets, supplying much of Therorem 4.5's existience result. Neu and Valko already obtain the same expected regret order using FTPL and counting-asleep estimators. The stronger hindsight guarantee and quantitative bit results remain valuable. but the presentation should distinguish these additions explicitly.
  • The runtime comparison does not evaluate the complete output pipeline at matched accuracy. Figure 1 reports CAT-FTPL's final-run runtime for obtaining low empirical marginal residual, excluding compact extraction and preceding doubling runs, while the LP baseline solves an expanded game. Moreover, Theorem 5.8 gives approximately T−1/4T^{-1/4} residual for the final compact strategy, compared with T−1/2T^{-1/2} marginal convergence, Figure 3b fixes the input marginals across extraction horizons, so it isolates extraction rather than testing the complete procedure under varying total budgets.
Questions for authors
  • Please explicitly separate the representation and regret results inherited from prior work from the new bit-complexity, hindsight-regret, and extraction guarantees. What is the precise additional guarantee relative to each closet predecessor?
  • Can you report the total runtime and availability-simulator calls required to produce final compact strategies at a common verified equilibrium tolerance, including learning, extraction, stopping, and residual evaluation?
2 comments
AuthorsOpenReview ↗

Response to Review

We thank the reviewer for their thoughtful comments and positive assessment of our paper. Please see our responses below. We have updated our submission PDF accordingly. Throughout, updates are highlighted in blue.

Weaknesses

W1: On preceding results/techniques

We agree that the relationship to prior work should be made clearer. We would like to clarify that our main contribution is a complete procedure for computing compact, playable approximate Nash equilibria in GSAS. The qualitative representation result follows by approximation from Azrieli and Rehbeck. However, our alternative proof allows us to establish quantitative bit-complexity bounds beyond existence: an ϵ\epsilon-NE can be represented using O(∣Ai∣log⁡(∣Ai∣/ϵ))O(|A_i|\log\left(|A_i|/\epsilon)\right) bits per player under independence (Theorem D.2 and Corollary D.4). Theorem D.5 shows that a general guarantee of this kind is not possible without independence.

Our learning algorithm builds on Neu and Valko and achieves the same regret bound, while strengthening their stated guarantee from max⁡τE[GT,i(τ)]\max_\tau\mathbb{E}[G_{T,i}(\tau)] to E[max⁡τGT,i(τ)]\mathbb{E}[\max_\tau G_{T,i}(\tau)]. The latter controls the best ranking for each realized learning trajectory and is the guarantee required for our equilibrium analysis, which requires additional technical machinery. This additional estimator analysis is given in Appendix B.10.

Finally, our recovery procedure converts the learned marginals into compact strategies with a finite-time equilibrium-gap bound (Theorem 5.8). Learning a marginal distribution alone does not provide this playable representation, as stated in lines 380-382.

W2: On runtime comparisons

Regarding Figure 1, we stated in Section 6 (lines 430-431) that “the computed solutions are not directly comparable in terms of output quality, but only in runtime.” The purpose of this experiment is to demonstrate the scalability problem caused by the expanded LP representation. With regards to scalability, note the LP runtime clearly exhibits exponential behavior, and a line-of-best-fit in logspace on the mean runtime for sizes ≥8\ge 8 predicts that solving a 15×1515\times 15 game would take around 1717 days, and the 150×150150\times 150 game our approach solves would take approximately 1013110^{131} seconds, which are far beyond feasible. Appendix C.2.1 (lines 1679-1684) specifies that the reported CAT-FTPL time is for the final run. The reviewer is therefore correct that this figure excludes preceding doubling runs and compact recovery.

Figure 3b does evaluate compact strategies recovered from CAT-FTPL marginals, following the procedure described in Section 5.2 (lines 402-404). As specified in Appendix C.2.2 (lines 1719-1724), the input marginals are obtained from CAT-FTPL with T=120,000T = 120,000 and held fixed while the recovery horizon varies. This isolates the recovery error. Figures 2b and 3b together corroborate Theorem 5.8. We have clarified this in lines 497-498 of the updated PDF.

To give a better idea of the end-to-end runtime of our method, we have modified Figure 1 to additionally include the wallclock time of a final run of CAT-FTPL followed by the compact recovery (Algorithm 3), stopping when the estimated SPR of the compact vector is below 0.050.05. We have modified the corresponding text to reflect this change, both in Section 6 and Appendix C.2.1. We have further added Table 3 in Appendix C.2.1, with the total runtime and availability samples across all runs (i.e., including preceding doubling runs). Tables 1 and 2 provide similar data for the final run only.

Questions

  • Q1: Please see our response to Weakness 1 above.

  • Q2: Please see our response to Weakness 2 above, particularly the addition of Table 3 in Appendix C.2.1. For instance, the mean total runtime (i.e., including all doubling runs) of CAT-FTPL followed by Alg. 3 to reach an estimated SPR≤0.05\text{SPR} \le 0.05 for the 100×100100\times 100 GSAS used in Figure 1 was 203 s203\text{ s}. For a 300×300300\times 300 GSAS, the mean total runtime was 707 s707\text{ s}. In comparison, the final runtime (i.e., excluding non-final doubling runs) for CAT-FTPL followed by Alg. 3 was 117 s117\text{ s} for the 100×100100\times 100 GSAS and 380 s380\text{ s} for the 300×300300\times 300 GSAS.

Thank you for the detailed response, the clarification separating inherited results(the qualitative representation from Azrieli and Rehbeck; the regret order from Neu &Valko) from the new contributions(quantitative bit-complexity bounds, the impossibility result without independence, the stronger E[max⁡τGT,i(τ)]\mathbb{E}[\max_\tau G_{T,i}(\tau)] guarantee, and compact recovery) addresses my first concern. Please keep this distinction explicit in the main text. The added end to end runtimes in Figure 1 and Table 3 answer my second question. I still see the T−1/4T^{-1/4} recovery rate and the lack of an accuracy-matched baseline comparison as limitation. Overall I maintain my positive assessment and keeping my rating of 3.

Reviewer_sFndOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies games in which each player privately observes a randomly drawn set of available actions and must select an action from that set. The authors formalize this setting as Games with Stochastic Action Sets (GSAS) and define the corresponding notion of approximate Nash equilibrium. Under independence of availability sets across players, they characterize equilibria through implementable marginal action distributions and show that these marginals admit approximate representations using compact weight vectors. For two-player zero-sum GSAS, they propose CAT-FTPL, establish ranking-regret guarantees, and obtain an O(T−1/2)O(T^{-1/2}) convergence rate for the time-averaged induced marginals. They further provide a stochastic approximation procedure for recovering compact strategies, whose final equilibrium-gap guarantee is O(T−1/4)O(T^{-1/4}) under fixed dimension and confidence.

Critical strengths
  1. An interesting extension of the standard game formulation. Random action availability captures feasibility constraints that are absent from ordinary normal-form games. The paper clearly illustrates that these constraints can change equilibrium behavior, so solving the underlying normal-form game is generally insufficient.

  2. A systematic theoretical treatment. The paper connects equilibrium characterization, regret minimization, and compact strategy recovery. The distinction between a marginal action distribution and an executable strategy is important, and the authors address both. The approximate bit-complexity results and the impossibility result without independence further clarify the scope of the representation guarantees.

Critical weaknesses
  1. The practical scope of the assumptions could be better motivated. The GSAS model uses a fixed, exogenous availability distribution, the main results assume independence across players, and the learning analysis additionally assumes i.i.d. availability across rounds. Although the paper identifies Markovian extensions and relaxing independence as future work, it would benefit from concrete applications in which the present assumptions are reasonable.

  2. The incremental contribution relative to sleeping-action learning needs a sharper comparison. Conditional on the interaction history, each player faces stochastic action availability and a history-dependent payoff sequence generated by the opponents. This closely resembles sleeping-action online learning. Moreover, the algorithm observes payoffs for every currently available action, making sleeping experts or restricted-information learning more precise comparisons than standard bandit feedback. The paper discusses related work and explains why sleeping external and internal regret are insufficient. However, a more explicit comparison with existing ranking-regret algorithms would help establish what additional analysis is necessary.

Questions for authors
  1. Under the independence assumption, which existing sleeping-action learning algorithms on ranking regret can be applied directly to each player’s learning problem? Do their guarantees control the expected pathwise ranking regret needed here against history-dependent opponents? What additional arguments are necessary for equilibrium computation and compact recovery?

  2. The introduction mentions trading and naval patrol applications. Could the authors develop a concrete application satisfying both Definition 3.2 and Assumption 3.3, specifying the players, actions, payoffs, and source of independent availability randomness? For the learning procedure, how plausible are i.i.d. availability across rounds and access to additional independent samples?

  3. Since Corollary 3 of Azrieli and Rehbeck gives Luce representations for all relative-interior feasible marginals, does Theorem 4.5 follow by approximation? Please distinguish the contribution of the alternative proof from the quantitative bit-complexity guarantees and computational recovery results.

  4. The discussion following Theorem 5.8 acknowledges that the recovery bound is loose. Is there evidence that the T−1/4T^{-1/4} rate reflects an intrinsic limitation of the procedure?

3 comments
AuthorsOpenReview ↗

Response to Review [Part 1]

We thank the reviewer for their careful reading and thoughtful comments. Please see our responses below. We have also updated our submission PDF according to the proposed changes. Throughout, updates are highlighted in blue. Our responses to your questions are in the subsequent comment.

Weaknesses

W1: On scope

The suggestion is much appreciated, as it would strengthen our motivation. We would like to give an example from security to illustrate our model. Consider an offline planning game between a transmitter and a jammer, each choosing an available channel or remaining idle. When both choose a channel, the transmitter receives a payoff of +1+1 when their channels differ and −1-1 otherwise, and the jammer receives the opposite payoff. Remaining idle for the transmitter gives it payoff −1-1 against every jammer action and remaining idle for the jammer gives the transmitter payoff +1+1 (with a tie giving transmitter payoff −1-1). Each player privately observes its available channels, and availability depends on the players’ independent local bandwidth (or local radio resources reserved for other tasks), drawn from fixed distributions and refreshed each episode. The transmitter and jammer can both always choose to remain idle. Thus, this is a GSAS as defined by Definition 3.2 that satisfies Assumption 3.3. A simulator that generates resource reservations provides additional independent availability samples where required. During self-play, recording the opponent’s chosen action allows the payoffs of all available actions to be computed, hence the learning assumptions fit independent simulation episodes. Similar examples can be given in settings outside of security applications. The description of this example is in lines 147-152 of the updated PDF.

W2: On comparison with existing methods

We thank the reviewer for suggesting this comparison. The reviewer is correct in saying that neither sleeping external (SE) regret nor sleeping internal (SI) regret work in our setting, as the counterexamples demonstrate. Nevertheless, note that the set of implementable marginals MiM_i is a convex hull induced by rankings, i.e., Mi=conv{μiτi:τi is a ranking}M_i = \mathrm{conv}\lbrace\mu_i ^{\tau_i}: \tau_i \text{ is a ranking}\rbrace, so ranking regret is naturally the right candidate. While prior work on ranking regret minimization (e.g., Neu & Valko (2014) [1]) already handles stochastic availability and history-dependent losses, and in particular, SLEEPINGCAT from [1] provides the same regret bound, the main distinction concerns the guarantee supplied by the analysis. To be precise, letting GT,i(τ)G_{T,i}(\tau) be the cumulative regret against some ranking τ\tau, their stated bound controls max⁡τE[GT,i(τ)]\max_\tau \mathbb{E}[G_{T,i}(\tau)], while our algorithm CAT-FTPL bounds E[max⁡τGT,i(τ)]\mathbb{E}[\max_\tau G_{T,i}(\tau)] instead. In other words, in their prior work, regret selects the best fixed ranking before taking the expectation over the learning trajectory, whereas our current ranking regret chooses the best ranking after the trajectory is realized. This is non-trivial and is the reason why we emphasized the term “pathwise”: indeed, our notion is stronger and can thus directly bound the expected saddle point residual of the averaged induced marginals. This also required some additional technical insights and machinery: our estimator uses geometric resampling, implicit exploration, and additional availability samples to obtain this guarantee without enumerating rankings (Appendices B.9-B.10), and we then recover a compact, playable strategy from the learned marginals, with the final equilibrium guarantee given by Theorem 5.8. We have added a clarification in lines 358-363 of the updated PDF.

AuthorsOpenReview ↗

Response to Review [Part 2]

Questions

  • Q1: Please see our response to Weakness 2 above.
  • Q2: Please see our response to Weakness 1 above.
  • Q3: The reviewer is right in saying that Theorem 4.5 follows by approximation from Corollary 3 of Azrieli and Rehbeck (2026) [2]: feasible marginals can be approximated by relative-interior marginals, which admit positive Luce representations. However, our independently developed Menon-Schneider argument provides an alternative and arguably simpler proof. Moreover, this result is a key element of our full computational procedure: indeed, our alternative proof technique is also used for the bit-complexity results (Theorem D.2 and Corollary D.4) and compact strategy recovery (Section 5.2), so it may be of independent interest. Finally, we would like to point out that the journal version of [2] was published very recently (10 June 2026), and we believe that it may be regarded as concurrent work. We have rephrased our writing in lines 264-269 of the updated PDF to make the precise novelty of our result clearer.
  • Q4: The reviewer has brought up an excellent question. The T−1/4T^{-1/4} rate arises because the RSA analysis bounds the expected squared ℓ2\ell_2 norm of the error, but SPR is controlled by the ℓ1\ell_1 norm of this error. We expect significant changes to the RSA procedure would be required to circumvent this and that handling boundary cases (i.e., target marginals on the boundary of the implementable set where some actions, when available, are always preferred over others) poses technical challenges that would constitute a valuable follow-up work. Our analysis therefore establishes convergence but does not show that this rate is intrinsic. Improving the rate remains an open question, and we have clarified this in lines 415-420 of the updated PDF.

[1] Neu, G., & Valko, M. (2014). Online combinatorial optimization with stochastic decision sets and adversarial losses. Advances in Neural Information Processing Systems, 27, 2780-2788.

[2] Azrieli, Y. and Rehbeck, J. (2026), Marginal stochastic choice. Theoretical Economics, 21: 373-401. https://doi.org/10.3982/TE6021.

Thank you for the detailed response. Your clarification of how the ranking-regret guarantee differs from prior work, together with the concrete GSAS example, has addressed many of my concerns. I am happy to raise my rating to 3 (weak acceptance).

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

The paper introduces a new type of game: games with stochastic action sets. These are normal-form games in which the players' available actions are stochastically drawn from a distribution. In particular, the paper focuses on two-player zero-sum games, and in particular with the assumption that the player's available actions are independent of each other.

The authors define and illustrate the setting, introduce equilibrium definitions, and show that (under this assumption) an equilibrium strategy can be approximated by compact, polynomially-sized weight vector (one weight for each possible action).

Then, they show how to use "ranking regret" (from sleeping bandit literature) in self-play so that the time-averaged marginal play converges to an approximate NE, and how to recover a compact representation of this strategy.

Finally, they perform experimental results and show that it works well.

I did not closely check the math and I have no prior knowledge of the sleeping bandit literature.

Critical strengths

This paper is remarkably well-written and easy to follow. It flows very well. Maybe I have been reading too many "slop" papers recently, but this sticks out as one of the most clearly written papers I've read. The didactic examples are especially nice.

The new setting seems like it is simple and therefore a valid contribution to game theory literature. The results are non-trivial. The paper includes both theoretical results and experimental results.

I think this paper is a "clear acceptance".

Critical weaknesses

I find no critical weaknesses, but here is a possible minor one:

One of the main results is that surprisingly, one can represent any implementable original-game-strategy using a compact vector. However, the authors note that a similar idea "has been studied in the literature of the Luce model of stochastic choice". It is possible that this makes the result in the paper somewhat less novel, although I do not have the context to evaluate this.

Questions for authors

A few nits/suggestions:

  • The abstract does a great job at conveying the ideas in the paper in a limited amount of space. However, it would be even more perfect if you could also squeeze in there that players observe only their own availability set.
  • In Theorem 4.5, is there a reason you say "Let \pi_i implement \mu_i \in M_i" instead of just "Let \mu_i \in M_i be implementable"? It gave me a modicum of confusion because \pi_i isn't used in the rest of the theorem or following paragraph. Is it because you are already talking about recovering \pi_i from \mu_i?
2 comments
AuthorsOpenReview ↗

Response to Review

We thank the reviewer for their thoughtful review and positive assessment of our work. We sincerely appreciate it and are glad to hear you found the paper well written. First, the reviewer commented that they “have no prior knowledge of the sleeping bandit literature”. We would like to clarify that our work is primarily game-theoretic, and the sleeping bandit techniques used are relevant insofar as they allow the computation of equilibria. This is analogous to the connection between external regret minimization and equilibrium computation in normal-form games, where the connection between ranking regret and Nash equilibria is specialized to our setting. The technical details in our paper are self-contained, and in particular, we do not expect readers to have familiarity with regret minimization in sleeping bandits: it is just meant to motivate our discussion and counterexamples for other “reasonable” but ultimately unsuitable notions of regret for GSAS. We hope that this can convince the reviewer to increase their confidence, since the relevant literature for this work is primarily the standard no-regret learning in games literature.

Weaknesses

W1: On novelty of results

We thank the reviewer for pointing this out. To our knowledge, prior works that derive a similar compact result are primarily in the economics literature (see Azrieli and Rehbeck (2026) [1] and references therein) and not for game-theoretic strategies. Crucially, our primary contribution is the computational procedure tailored to the GSAS setting that allows for the recovery of these compact strategies with a saddle-point residual bound. In this sense, the existence of such strategies can be thought of as the “starting point” of our analysis, and still requires additional results to obtain something computationally meaningful. Finally, we would like to point out that the journal version of [1] was published very recently (10 June 2026), and we believe that it may be regarded as concurrent work. We developed our proof independently, using linear algebraic techniques that are arguably simpler, before becoming aware of their work. This technique we developed was also used to prove the bit-compactness results in Appendix D, going beyond the existence result (cf. Remark 4.7).

[1] Azrieli, Y. and Rehbeck, J. (2026), Marginal stochastic choice. Theoretical Economics, 21: 373-401. https://doi.org/10.3982/TE6021.

Questions

  • Q1: We will add to the abstract that each player observes only their own availability set (see the updated abstract, highlighted in blue). Thank you for the suggestion.
  • Q2: To clarify, we say that a marginal μi\mu_i in MiM_i is implementable if there exists some strategy πi\pi_i that implements μi\mu_i. The reviewer is correct in that we ultimately care about πi\pi_i (as this is the strategy that a player can actually use to play the game). The reason for the wording in the theorem is to clarify that we establish existence of some πi’\pi_i’ that approximately implements the same marginal as πi\pi_i, with the association being in terms of their respective marginals μi’\mu_i’ and μi\mu_i.

Thank you for the response. Although the response clarified the genuine novelty of the results and that no prior sleeping bandits context is needed to evaluate the paper, I maintain my score (clear acceptance) and confidence (2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.