Protocols for Verifying Smooth Strategies in Bandits and Games
Authors: Miranda Christ
Daniel Reichman
Jonathan Shafer
Venue: NeurIPS 2025 poster ()
Keywords: Multi-armed bandits
Interactive proofs
Normal-form games
Primary area: theory
TL;DR: We show how to efficiently verify approximate optimaility of smooth policies and strategies in bandits and games

Abstract: We study protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries to the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action and provide protocols for verifying that a smooth policy for a multi-armed bandit is close to optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, we show how to use cryptographic tools to reduce the communication cost of our protocols. We complement our protocol by proving a nearly tight lower bound on the query complexity of verification in our settings. As an application, we use our bandit verification protocol to build a protocol for verifying approximate optimality of a strong smooth Nash equilibrium, with sublinear query complexity.

Protocols for Verifying Smooth Strategies in Bandits and Games
Miranda Christ
Daniel Reichman Worcester Polytechnic Institute daniel reeiiel.reiee chman@gmail com
Jonathan Shafer MIT shaf eanferroomi.o. edu
Columbia University mchristécs.
columbia. mchrist@cs.columbia.
edu
Abstract
We study protocols for verifying approximate optimality of strategies in multi- armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action and provide protocols for verifying that smooth policy for a multi-armed bandit is close to optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, use cry cryptographic tools to reduce the communication cost of our protocols. We complement protocol by proving nearly tight lower bound the query complexity of verification in our settings. As an application, we use our bandit verification protocol to build protocol for verifying approximate optimality of strong smooth Nash equilibrium, with sublinear query complexity.
show how to
Introduction
An overabundance of available actions makes decision-making challenging in numerous settings, from consumer choice to logistical operations and public policy. To gain information about the (often stochastic) reward an action entails, agent can simply perform that action and experience the outcome. However, in many situations it is infeasible for an agent with limited resources to try even a small fraction of the set of available actions. One method to mitigate such choice overload is to rely on an external source providing information about the utility of actions. For example, one may consult recommendations from other customers when deciding whether purchase product. or solicit advice from consulting firms when formulating a business strategy or public policy. This information however, may be unreliable, and accuracy. Namely, can one outsource information collection to an untrusted external party, and verify correctness by independently assessing the utility of just few actions?
clear how to efficiently verify its
Verifying utility estimates arises in machine learning (ML. applications as well. For example, an end user may delegate MI. training better-resourced but untrusted external party [Goldwasser eet al. 2021 2015). In reinforcement learning, training algorithm might return set of estimates for the rewards of possible actions. Once again, challenge for the user to verify the fidelity of these estimates, which could be inaccurate for numerous reasons. For example, the external party could be malicious, careless and susceptible errors, or the training algorithm may be faulty. To address this challenge, a line of research develops learning methods that are robust to adversarial data corruption [Charikar al. 2017 Canetti and Karchmer, 202T]. The specific case of corrupted
rewards (utilities) in multi-armed bandits has received attention as well [Jun et al. 2018 Zhang et al. 2022.
Similar verification issues emerge in multiagent settings studied game theory, where each agent's utility may depend on the other agents' actions. An object of central interest in such settings the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(E- (e-approximate) Nash equilibrium (NE or E-NE), which is a strategy profild" such that no agent can improve their own utility (by more than E) by deviating unilaterally another strategy. There is host of questions related to verification and Nash equilibria; specifically, the current paper is motivated by scenarios such as:
An agent might want to verify that, given that the current strategies of the other agents are known, proposed strategy is (approximately) the best possible. For instance, suppose Alice is a corporation navigating a complex market, and she receives advice from a consulting firm that recommends specific strategy म. Alice might subsequently like to verify that the proposed स is indeed an (approximately) optimal strategy given current market conditions (i.e., given what other market participants are doing).
An agent might want to verify that, together with the known current strategy profile of the other agents, proposed strategy forms an (approximate) Nash equilibrium. For instance. in the previous example, assume the proposed strategy गे indeed has optimal expected utility for Alice in current market conditions. Nonetheless, adopting strategy might not be good idea if, in the case where Alice follows strategy म., some other market participant, Bob, can unilaterally deviate to a strategy that benefits Bob but significantly damages Alice. Therefore, Alice might like to verify that, together with the current known strategy profile of the other market participants, the proposed strategy forms an (approximate) Nash equilibrium. That would be consistent with म being reasonable strategy for Alice to commit to.
We consider two popular models for problems of choosing between different actions: multi-armed bandits (MAB)Lattimnn and Szepesvári [2020] in the single-agent setting, and normal-form games in the multi-agen setting. For both MAB and games, we consider the settings where n, the number of actions available to each player, is a large integer. The large number of actions, along with the prohibitive computational cost of computing approximate NE [Daskalakis et al., 2009 Rubinstein 2017]. motivates the reliance on advice from external parties. This leads to the following questions:
Question 1. Given MAB with arms, can we verify whether list of purported rewards is close to the true rewards and outpul a near-optimal strategy, using a number of bandit queries that is sublinear in u??
Question 2. Given k-player, n-action normal-forn game, can a prover convince a verifier that a strategy profile is an E-NE, with the verifier making a number of payoff oracle queries that is sublinear in n?
We address these questions within the framework of interactive proof systems [Goldwasser et al. 1989.. In this setting, a computationally bounded verifier interacts with an untrusted prover, and can verify the correctness of statements that are intractable to assess without interaction [Shamir] 1992]. A recent development in the study of interactive proofs is the application of this methodology to machine learning Goldwasser et al.) 202T). We adopt this development in our setting of verification in MABs. MABs are fundamental concept in machine learning and are used in numerous theoretical and applied settings. Therefore, we hope that our study could lead to further discoveries regarding the potential uses of interactive proofs in machine learning and operations research. We focus on the offline setting of MABs and do not consider regret minimization. Studying interactive proofs for the online setting is an interesting direction for future work.
Let us first give a simple example where the verification of an MAB can be significantly more efficient compared to finding optimal or near optimal strategy. Consider the promise problem where an MAB is known to have a single arm whose reward a deterministic reward of 1, and all other n - 1 arms have deterministic reward of O. It is trivial to verify that given arm communicated by a prover guarantees a reward of 1 using a single pull to that arm. On the other hand, finding such an arm can require 2(n)) pulls to the arms: if the single arm with reward one is chosen uniformly out of n arms, a linear number of queries to the arms of the bandits is needed to find it [Kearns et al. 2002 Mannor and T sitsiklis 20044).
Similarly, for a given parameter y it can be verified with probability at least 2/3 that an MAB (with rewards in [-1, 11) has arm with expected reward at least 7 for some accuracy parameter using ( queries to an arm provided by a prover. As before, finding a strategy with an expected
reward of requires ((n) queries to the arms of the MAB.
A strategy is distribution over actions. A strategy profile is an assignment of a strategy to each player (i.e., agent) in the game.

---

Observe that in the first example, we have a promise problem in the sense that we know that there exists single arm with reward 1 and that this is the arm with the highest reward. In the second example, we verify a lower bound on the value of an optimal strategy, but we do not verify an upper bound on the best possible value, D hence we do not verify that a given strategy is nearly optimal. This is not a coincidence: Even in the interactive proof setting, we show that ( queries are necessary. Therefore to achieve verification with a sublinear number of queries to the arms of the bandits, we need to make additional assumptions on either the MAB, or the set of strategies considered. Here we show that verification with a sublinear number of queries to the arms of the bandit is possible for smooth strategies discussed in the next section.
In interactive proofs, the number of bits communicated between the prover and the verifier may become a bottleneck. Therefore, it is desirable to have communication efficient protocols where the number of bits communicated is sublinear in n as well. We consider communication-efficii protocols in the setting where prover wishes to convince the verifier of the value of the optimal policy, but does not need send the optimal policy itself. We show that such communication-efficie protocols can be achieved for sufficiently smooth MABs by using cryptographic primitives such as vector commitments and SNARKs, While our basic protocol consists of just a single message sent from the prover to the verifier, our protocol with sublinear number of bits of communication uses multiple rounds of interaction.
2
Verifying smooth strategies: model and results
2.1 Smooth strategies: motivation and background
A smooth strategy is a distribution over actions that is not too concentrated on any one action. More precisely, a strategy is a-smooth if each action is selected with probability at most Clearly a E [1/n, 1]. with smaller values of a corresponding to smoother (i.e., closer to uniform) distributions. To ensure that our protocols have sublinear query complexity, it is needed that on o(n). This is a natural assumption to ensure that the distribution is "well spread" in the sense that the support size of the distribution tends infinity with n.
As a motivation, in many applications each arm in an MAB represents some resource that a system can utilize (c.g., server in a data center, driver in a ride-hailing service). Often, as the system grows, the number of available arms increases, as does the total number of arm-pulls, but the capacity of each individual arm remains bounded (e.g., as ride-hailing service grows, the total number of rides and drivers increase, but the number of rides each individual driver can handle remains the same). If the total number of arm-pulls is, say, linear in the number of arms, then the MAB policy must be o-soohth with o = O(1/n).
In MAB, strategy is s-optiall omsooohh strategy if it is o-smooth and there is a-soooth strategy with a utility that is greater by more than E (Definition 5.3). In a normal-form game, a strategy is E-approximate strong o-smooth NE if every player's ' strategy is o-smooth, and no player can unilaterally deviate to a o-smooth strategy that improves their expected payoff by more than E.
We stress that the optimal smooth strategy can have significantly worse expected utility compared to the best unconstrained policy. For example, suppose a 1/k for some integer k >> 1 and that a single arm has utility 1 whereas all others have utility O. Here the optimal unconstrained policy has utility 1, while the optimal o-smooth policy has utility 1/k. This "cost of smoothness" can be quantified as i1 - 1 Σ us where i1 2 U2 2 uz are the utilities of the arms sorted in decreasing order. This holds simply because the optimal o-smooth policy assigns equal weight the top k arms, while the optimal unconstrained strategy has utility u1.
The key property of smooth strategies of not putting too much mass on any particular action can be used to model unpredictable players whose strategies cannot be captured by a "small" set of actions that characterizes their actions. Such strategies can prove beneficial when predicting the move of a player can result in significant negative utility (loss) for such a player. Perhaps surprisingly. our results show that properties of games with unpredictable players allow for efficient (sublinear) verification. Daskalakis et al. (2024) study smooth strategies in games. They provide additional
2 Inffrmallly in the language of interactive proofs, the aforementioned verification procedure has the com- pleteness property but not soundness.
3

---

motivations for studying smooth strategies, and note that a strong o-smooth NE (where E = 0) is
guaranteed exist in every normal-form game.
As noted, the study of smooth strategies in the context of normal-form games was recently proposed by Daskalakis et al. [024]] One motivation for their study of smooth strategies comes from the area of smoothed analysis (Spielman and Teng 2009] which studies the influence of random noise on the time complexity of algorithms. There are at least two ways of studying the smoothing influence of noise on complexity issues in games and MABs. One is to assume that the instances (e.g., the payoff matrix of the normal form game) are subjected random noise. The other, which we focus on here, is to consider smooth strategies for players: namely distributions over actions that do not assign too much mass to any one action. For example, for MABs we seek strategies that maximize the expected reward, subject to the constraint that the strategy is smooth distribution. Daskalakis et al. (2024) observe that distributions that are perturbed with random noise often have such smoothness properties. Additionally, those authors provide several further motivations for studying smooth strategies in games. They also discuss how smooth strategies can be used to generate behavior that more similar in style to humans. Furthermore, elaborated by Daskalakis et al. [2024] smoothens is related to several equilibrium notions in game theory.
2.2 Our setting
Verification in multi-armed bandits. In this setting, both a prover and a verifier have access to an n-armed bandit. This access is given via an oracle: one can query the oracle by specifying an arm, and in return receive reward drawn from that arm's utility distribution. The prover and verifier communicate interactively, and at the end of the interaction the verifier either rejects or outputs a policy. If both the prover and the verifier follow the protocol, the verifier should output an approximately optimal smooth policy with probability at least 2/3; this property is called completeness. The protocol should also satisfy soundness, in that even if the prover behaves arbitrarily, the verifier should output a non-optimal or non-smooth policy with probability at most 1/3. Finally, the protocol should be efficient in that both the prover and verifier run in polynomial time, and the verifier makes o(n)
queries 3
Verification in normal-form games. We give high-level overview of our results due to space constraints: details can be found in the supplementary material as well as the arXiv version Christ al. 2025)] In this setting, both the prover and the verifier have access to a k-player, n-action normal-form game. This access is given via a game oracle: one can query the oracle by specifying a strategy profile and in return receive vector of payoffs (one per player) corresponding
tuple of actions drawn from the specified strategy profile. The prover and the verifier are both given an explicit description of proposed strategy profile n, well as an optimality parameter E, smoothness parameter o, and a slackness parameter 17. The prover and verifier communicate interactively. and at the end of the interaction the verifier either accepts or rejects. Analogously to the MAB setting, this protocol must satisfy completeness and soundness. Completeness requires that if both parties follow the protocol and æ is indeed an e-approximate strong o-smooth NE, the verifier accepts with probability at least 2/3. Soundness requires that for any (possibly malicious and computationally unbounded) prover, if क is not an (e + -)aaapproi strong amsoohh NE, the verifier rejects with probability at least 2/3. We note that adapting the MAB verification for verification in games requires certain technicalities such as introducing an additional slackness parameter rj. Details can be found in the Games Section in the Supplementary Material.
2.3 Our contributions
We give a high-level overview of our results. Formal statements and proofs can be found Section and in the full version Christ et al. [2025]. We construct interactive protocols for MABs and normal- form games, where both the verifier and prover have polynomial running time in all parameters. We also present corresponding lower bounds, showing that verification using our protocols is strictly more efficient than learning in terms of query complexity, and that our protocols have near-optimal dependence on key parameters.
5
3 As usual, is possible to efficiently amplify the success probability from 2/3 to arbitrarily small, both our protocols for handits and the protocols for games. As in Footnote |

---

1. Efficient verification for MABs. We construct protocol for verifying e-optimal o-smooth strategies where the verifier makes O(on/E²) queries to the MAB oracle. The protocol consists of a single Ó(n) --bi message sent from the prover to the verifier. A formal statement is given in Theorem 5.5
2. Lower bounds for MABs. We prove a matching lower bound of (((rn//") on the number of queries needed by the verifier in any such MAB verification protocol. We also prove that learning upproximately-opiee
smooth strategies requires (())) queries, which (together with verification protocol) implies that verification can be more efficient than learning. A Formal statement appears in the Multi-armed bandits Section in the Supplementary Material.
3. Lower communication using cryptography. We show how to obtain an interactive proof for the value of the optimal smooth policy of a bandit, where the asymptotic number of arms pulls is the same as in our original protocol. The prover now sends at most (A (no (1/=)/E) bits while affecting the probability of correctness by a negligible additive error: A constant À suffices to ensure an additive error of at most 10-0, Therefore, assuming no /s o(2), we have a protocol with sublinear communication. A formal statement is given in Theorem 5.6
4. Efficient verification of smooth NE in games. For normal-form games with k players and n actions, we construct an interactive protocol for verifying that a given strategy profile is an approximate smooth NE, with slackness 1) > That is, the verifier accepts if the input strategy profile is an E-approximate o o-smooth NE, and it rejects if the input strategy profile is not an (E + 17) aappoxximate o-smooth NE. The verifier uses (kon/n?²) queries the game oracle. The full statements and proofs appear in the Games Section in the Supplementary Material.
In contrast, for constant E, Theorem 4 in Rubinstein 2017] states a lower bound of (0(k)) queries to the game oracle for computing an 6-NE without the help of a prover, and this lower bound extends also to computing g-smooth s-NE for & constant and o O /m) (see Remark 12 in Daskalakis et al. 2024 [] Thus, our verification protocol offers substantial savings in terms of k as well. We also provide a linear matching lower bound based on similar ideas of the lower bound for verifying MABs.
2.4 Proof ideas
Our bandit verification protocol relies on the following observation. Consider lying prover trying to convince a verifier that a given a-smooth bandit strategy π is approximately optimal, although there exists another a-smooth strategy n² whose expected reward exceeds that of a by more than e. Consider protocol that requires the prover to provide a good estimate of the expected utility of each arm. Because x' is smooth, follows that in order to conceal the existence of '²" the prover must lie about the utilities of many arms. Thus, it suffices for the verifier to independently estimate the utilities of a few randomly chosen arms, and reject if any of the prover's purported utilities are too far from the verifier's estimates. Importantly, whereas the prover must lie about many arms, it is enough for the verifier to catch just one lic. In particular, if the prover lies about an fraction of utilities, the verifier only needs to query roughly 1/3 arms in order to detect the lie with constant probability. In more detail, assume that the verifier is promised that, if the prover is lying enough to require rejection (the lie distorts the utility of the optimal policy by at least e), then the prover is in particular lying by more than a on at least a B fraction of the arms for some specific known values o, B > 0. This knowledge implies that Bnoo 2 e and also a 2 Based on the promise, the verifier can detect the lie by pulling O ) arms which by the above inequalities is at most O(na/e /e²). While a, B are not known, the verifier can use a simple partitioning scheme to guess them, which adds a logarithmic term the query complexity of the verifier.
Our lower bound of (onn/E? on the number of queries needed for MAB verification relies on a reduction to the coin problem where one needs to decide with a few queries whether given coin has bias 1/2 & or bias 1/2 + e. Our proof uses ideas from Even-Dar et al. 2002
RRmarr 12 in Daskalakis et al. 2024 refers to the case where and a are both constant. However, as discussed in Footnote 8 this corresponds to @(1/n) in notation for smoothness.
5

---

Using succinct non -on-interactive arguments of knowledge (SNARKs) and vector commitments, we significantly reduce the communication between the prover and the verifier in our bandit verification protocol (the Preliminaries Section gives more details about these cryptographic tools). A vector commitment allows one to commit to a vector and reveal individual components whose consistency with the commitment can be proven. The commitment and opening proofs require space independent of the length of the vector. A SNARK allows prover to succinctly prove that a given instance belongs to polynomial-time computable relation.
central observation in our NE verification protocol is that we can use the bandit verification protocol to ensure that no player has profitable smooth deviation from a proposed strategy profile æT That is, for each E [n]] if all players except player behave according to the profile π,, then player i is choosing between n actions, each of which has some fixed reward distribution - This is exactly an n-armed bandit. So player has no profitable smooth deviation if and only its current strategy an optimal smooth strategy for an appropriately defined bandit. Our NE verification protocol essentially performs this bandit verification times, once for each player. We also show that a linear dependence on k is necessary.
Related work
There is a substantial body of work studying algorithms for MABs for finding a distribution over actions (or single action) that maximizes expected utility [Lattimore and Szepesvári 2020 Garivier and Kaufmann 2016). Several works demonstrate a lower bound of [2(z)) (where n is the number of arms) on the number of arm-pulls that are needed to find strategy that maximizes utility for
the player [Karnin et al. |013] Chen and Li 2013 Chen et al. 2017 | Mannor and Tiissiklis 2004a|
Even-Dar et al. 2002] Assadi and Wang 2022] Specifically, Even-Dar al. [2002] provides an algorithm for identifying the best arm up to an additive error of E with probability of success at least
1 1- They achieve query complexity of On log(1/8)/e²) improving the naive algorithm whose query complexity is O(n log(n/ (og Furthermore, they complement their result by providing a matching lower bound on the query complexity of any algorithm achieving such error guarantees in the PAC framework based on a reduction to the coin problem. A lower bound of O(n log( 1 was obtained using different methods in Mannor and Tsitsiklis [2004a]. They also show lower bound of 2 )
(n (n+ + (og((/6))) for the case where the vector of utilities of the arms is known (but it is not known which arm has which utility) and the goal is find the arm with the largest expected utility. There is also extensive work on regret minimization strategies in MABs [Lai and Robbins 1985). a setting that we do not touch on in this paper.
A rich line of work examines the complexity of finding Nash equilibria (NE). The problem of finding an approximate NE in a normal-form game with least 3 players is known to be complete for the complexity class PPAD [Daskalakis et al. 2009]. Even for the seemingly simpler case of 2 players, computing exact NE is PPAD-complete [Chen and Deng |006). and computing an approximate NE is hard under the Exponential Time Hypothesis for PPAD [Rubinstein| [017]. While finding a NE hard, verifying that given strategy profile is an (approximate) NE can be done in polynomial time Finally, the study of the query complexity of approximate NE in 2-player normal-form games has received significant attention [Babichenko 2019 Fearnley et al. 2013 Göös and Rubinstein 2023]. It is known [Göös and Rubinstein 2023 that the trivial upper bound of n² is nearly tight: In certain games ((n==(() queries may be needed to find an approximate NE.
The intractability of finding NE e-NE in arbitrary normal-form games motivated Daskalakis et al. 2024] to introduce the notion of o-smooth NE where each player places a probability mass of at most [/(no) for each of the actions and is a smoothness parameter in [1/n, 1] (their parametrization of smoothness differs from ours: recall that we call a strategy smooth if for every action the mass on the action is most σ). They consider two equilibrium notions related to smoothness: in strong o-smooth NE, each player is executing a smooth strategy and cannot improve their utility by deviating unilaterally their utility by deviating unilaterally to a smooth strategy; however, the strategies of players in a weak amoooth NE need not be r-smooth. Analogous notions are defined by Daskalakis et al. 2024
smooth strategy. In a weak o-smooth NE, again no player can improve
'The reward distribution each action is fixed, because the reward distribution is a function of the strategies of the remaining players, which are fixed according to .. This is true for any problem in FNP, of which PPAD is subset.

---

for e-approximate (smooth) NE where players cannot improve their utilities by more than E. For strong E e-approximate o-smooth equilibrium, Daskalakis et al. 2024] prove there exists an algorithm for finding such an equilibrium in time n [K' log(k/s)/=") where k: is the number of players. For weak e-approximate a-smooth NE, they offer an algorithm with runtime complexity independent of n. (the runtime depends only on the number of players k, the smoothness parameter and the approximation parameter E).
Several works study interactive proof' for machine learning Goolwasser et al. 2021 Mutreja and Shafer 2023 Gur et al. 2024 Caro et al. 2024b al Their main focus on verification in supervised learning and similar settings. For instance, verifying that a proposed hypothesis satisfies the agnostic PAC requirement with respect to a (fixed and known) hypothesis class and a (fixed but unknown) population distribution, using less access (samples queries) to the population distribution than necessary for agnostic PAC learning. The questions of verifying MAB strategies and NE in normal-form games with few queries to the bandit or game oracle are not studied there.
4 Preliminaries
Let = f1.2.3.... For n N, we denote by [n] the set the set of actions of players both in MABs and games is [n]. For set Ω2 write A denote the set of all probability measures defined on the measurable space (2, where F is some fixed o-algebra that is implicitly understood. We often identify distribution p ([n)) with the vector
n and assume throughout that
p = (p1.....PP) such that pt = p(i) = Pa=pll= = i). Finally, we define the notion of a smooth distribution:
Definition 4.1. Let n E Nand a E (1/n, 1}. A probability distribution for every i [n]. Ps S
(mn) is called smoohhh
The degree of smoothness of a distribution is governed by the parameter a. For = 1, smoothness vacuous as every probability distribution is I-smooth. On the other extreme, when o = 1/n the distribution is the smoothest possible: the uniform distribution.
5
Bandits
5.1 Definitions
Definition 5.1 (Bandit). Letn N. An n-arm bandit is vector o distributions (g1...., ..., (A((0, 1]))".
A bandit defines bandit oracle such that, given a query E [n]] (corresponding to "pulling the i-th arm of the bandit") the oracle returns utility z ~ q. sampled independently of all previous oracle queries and responses.
The expected utilities vector of q is a vector u = utility (q) E [0, 1]"h such that un = Rarng [x] for all i [n]. A strategy for n-arm bandit is a distribution
utility of i with respect is Eiso, [x] " n2U; - ... A(m))). The expected
Definition 5.2 (Smooth bandit strategy). Let n E N and E [1/n, 1). A strategy x E [(ml]) for an n-arm bandit a-smooth if T. S a for all
[n].
Definition 5.3 (Optimal smooth bandit strategy). Let n E N. > 0, a [1/n, 1]. let [0, 1]mh be the expected utilities vector of an n-arm bandit, and let E [m))) be a strategy. We say that n is e-competitive with respect to a-smooth policies for u, if for every osmooth strategy n' E A([n]).
n'' USE.
If in addition π is a-smooth, then we say that æ is an E-optimal a-smooth strategy for u Definition 5.4 (Verification of optimality for smooth bandit strategies). An interactive proof system for verification of copttmal o-smooth policies for n-arm bandits is pair of algorithms (V, P) such
These are special cases of definitions in Daskalakis et al. 2024 The first definition corresponds to a weak e-approximate omoshhhh Nash equilibrium for and the second definition corresponds to strong e-approximate o smmoooth Nash equilibrium for where o' = 1/(no).
7

---

that for all n E N, and for every n-arm bandit with expected utilities vector utility(4) E [0, 1 and bandit oracle Og and for all a E [1/n, and 2 the following two conditions hold:
Completeness. Let the random variable (n, Wv [ 0), po (n, e,) A(ni)) U (reject)
denote the output of V after interacting with P, when each of them receives (n, E, o) as input and has oracle access to Oq. Then
[[( + reject) (V o-smooth x' E A((n)) u TT S
Soundness. For any (possibly malicious and computationally unbounded) prover Pl (which in particular may depend on n, E, a and q), the verifier's 's output TT = [vog(n, P'] E A(In) freject) satisfies
[ = reject) V (A a-smooth x' A([n)) u u Ty S E)] 2
In both conditions, the probability is over the randomness of Og and V, as well as P or P'. Theorem 5.5 (Verification for bandits), Let E N, let E [1/n, 11. let 2 0. There exists interactive proof system (V, for verification of E-optimal o-smooth policies for n-arm bandits such that:
The protocol consists single message of O(n (og(1/e)) bits sent from P V.
performs m (n.lo(nn/E)/z²) nonadaptive queries the bandit oracle and runs in time poly(n, 1/c).
VV performs
my = 0 no E²
no
!
log
log
nonadaptive queries the bandit oracle, and runs in time poly(n, 1/2).
In particular, if ((1vm)) then my = =((v)) and if = ((1/n) then my is independent of n.
The pseudocode of the verification protocol and the proof of Theorem 5.5 appear in the Multi-armed bandits Section in the Supplementary Material.
5.2 Vector commitments
Cryptography preliminaries
Let E denote the security parameter. We write p.p.t. to mean probabilistic polynomial time. We let negl(A) denote a function that is O(1/X²) for all 0.
vector commitment [Catalano and Fiore 2013 a tuple of p.p.t. algorithms:
KeyGen(1* n) - pp: takes as input the security parameter and size n of the vectors be committed, and outputs public parameters pp.
Commitpo - Cu, aux: takes as input length-n vector v, and outputs a commitment c and auxiliary information aux. aux often contains the entire committed vector e.
Open i, aux) + pf: takes as input a value v; an index i, and auxiliary information aux. It outputs proof pf that e; is the 5th component of e corresponding to aux.
Verify (Co, 04, pf) > {accept, reject]:: takes as input a commitment cos a value v; an index i, and proof pf. It accepts if and only G, commits to vector whose 7th component is U/-
Vector commitments must satisfy correctnsss and position binding. Correctness requires that with overwhelming probability, any honestly generated public parameters and honestly committed vectors yield valid opening proof' for all of their components. Position binding requires that it is infeasible for any non-uniform p.p.t. adversary to produce commitment and two valid proofs for different openings of that commitment. For precise statements, please see the Cryptography Section in the Supplementary Material.

---

5.3 Succinct non-interactive arguments of knowledge
In our protocols we use succinet con-interactive arguments of knowledge (SNARKs). More informa- tion regarding SNARKs can be found in Groth (2016].
A succinct non-intenn -oniintercctive argument of knowledge for relation generator R is tuple of p.p.t. algorithms:
Setup(1>, R)) pp, 7: takes input the security parameter and relation R E R. and outputs public parameters pp and simulation trapdoor 7.
Prove( R, pp, w) + pf: takes as input a relation R, public parameters pp, and statement- witness pair (Ø, w) R. It outputs proof pf of this pair's membership in the relation.
Verify(R, pp pf) - {accept, reject): :: takes as input a relation R. public parameters pp. statement Φ, and a proof pf. should accept if and only if Φ has a witness such that (Ø, w) E R.
We consider SNARKs that satisfy perfect completeness and computational knowledge soundness.
Perfect completeness requires that for all À E N, R E R, and (ø, w) E R: (pf Prove R, pp, o, w) accept < Verify (R, pp, pf)]
Pr (pp,7) Setup- (R)
Computational knowledge soundness requires that there exists a non-uniform p.p.t. extractor that can extract witness whenever adversary can compute an accepting proof. That is, for all non-uniform adversaries A, there exists a non-uniform p.p.t. extractor N'A such that
(ø, w) & R and Verify(R,, R, pp, o, pf) + accept
(R, - ((1A)) (6, - Setup(1))
Pr
S neg)(A),
w) (A) (,,
where (AII denotes that the extractor has access the adversary's 's internal state and randomness.
5.3.1 A low-communication protocol variant
Here we outline how to use vector commitments and SNARKs in a new protocol with lower commu- nication cost by having the prover send commitment the vector à of purported rewards, rather than sending ü in full. It uses SNARK to prove that the optimal smooth policy with respect to has claimed value. The verifier then proceeds exactly in the smooth bandit verification protocol; but instead of examining ū directly at each index, it asks the prover for the value and opening proof. Below, we sketch the ideas behind the proof of correctness. The implementation of the protocol as well as the bandit verification protocol on which the low communication variant builds on, can be found in the Bandit Section in the Supplementary Material.
Theorem 5.6. Let X N be the security parameter, let N, let (0,1), let q be n-armed bandit, and let u denote be the vector of expected urilities of q. There exists a protocol with the following properties. The protocol consists of trusted setup phase, in which shared parameters are generated by trusted entity; and an interactive phase between a prover and a verifter. Assuming the security of the underlying SNARK TI and vector commitment VC, our protocol satisfies:
Completeness: If the prover behaves honestly, the verifier outputs a value I that is within of the value of the optimal a-smooth policy with probability at least 3 neg
Even if the p.p.t. prover behaves arbitrarily, the probability that the verifier outputs a value that is not within & of the optimal value is at most 3 + negl(A).
Soundness:
The efficiency of the protocol is as follows:
II has constant-sized proofs, and VC has constant-sized commitments and opening proofs, the protocol consists of 0() (no log"((/E)// bits sent between P and V.
P performs m. On nonadaptive queries the bandit oracle and runs in time poly(n, 1/s).

---

V performs
my 0
no 62
no
1
log
log
nonadaptive queries the bandit oracle, and runs in time poly(n, (n, 1/e).
Proof. Communication The prover sends commitment and SNARK proof, each of which consist of (()) bits. In the interactive phase, the verifier sends (a, log(1/e)) O(nor log (1/e)/e) indices, each of which can be written in log(1/e) bits. The prover sends O(a log (og()/)) openings and opening proofs, requiring O(na log" (1/c)/c) bits in total. The number of queries made by the prover and verifier to the bandit oracle is identical to in bandit verification protocol.
We prove the soundness of the protocol. Completeness is proved the Supplementary Material.
Soundness Towards a contradiction, consider a p.p.t. adversary A that acts as the prover and with probability at least 1/3 1/poly(A) causes the verifier output that is e-far from the true value of the optimal a-smooth policy for some bandit q. Recall that computational knowledge soundness of II implies that there exists a p.p.t. extractor X'A that, with overwhelming probability, computes nn.. That is, Co is a commilment to ir, π is indeed an optimal a-smooth policy for ū, and the value of ı is indeed Now, position binding the vector commitment implies that with overwhelming probability all openings of i that the prover sends to the verifier are either rejected, or indeed match the corresponding component of ü.
(T, ū) such that (Ca, Cus t; π, ū) E Rvc. pp.n.
Soundness of the protocol now follows exactly from the analysis of the bandit verification protocol.
We remark that there exist SNARKs with constant (O(A))-sized proofs for arithmetic circuit satis- fiability, which have knowledge soundness in the generic group model [Groth] 2016). There also exist vector commitments with constant-sized commitments and opening proofs; for example, the CDH-based scheme of Catalano and Fiore (2013
6 Conclusion
We have studied protocols to verify near optimality of protocols and strategies for MABs and games. natural direction to study interactive proofs for near optimality of policies in Markov Decision Processes Sutton and Barto (2018) with horizon larger than 1. It appears that additional ideas are needed in this setting to deal with the network structure associated with the transitions the MDP which is absent in the MAB setting. Additionally, empirical validation of the protocols here is of interest.
Many games include multiple sequential actions of players. Such games are often represented in extensive-form. Devising protocols verify properties of strategies in extensive-form is an interesting future research direction.
Acknowledgments and Disclosure of Funding
MC was partially supported by Google CyberNYC grant, an Amazon Research Award, and NSF grants CCF-2312242, CCF-2107187, and CCF-2212233. JS was partially supported by NSF CNS- 2154149, an Amazon Research Award, and by Vinod Vaikuntanathan's Simons Investigator Award.
References
Sepehr Assadi and Chen Wang. Single-pass streaming lower bounds for multi-armed ban- dits exploration with instance-sensitive sample complexity. hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neu- ral Information Processing Systems 35: Annual Conference on Neural Information Pro- cessing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, November 28 Decem- ber 9, 2022, 2022. URL. http::/paperss.......//// nips. cc httpeccccppppefieaeee wilelffilll//eeeeeeeeeeee (Gecccbocc1844777911cc6666622223 ootpr///eeeeeeaattttttttto-ooeee htmml
Sanmi Koyejo. S. Mo-
10

---

Yakov Babichenko. Informational bounds on equilibria (a survey). SIGecom Exch., 17(2)225 -45 2019. doi1100.145/338122..33.333 URL /tt 1141/3381131111/ 33811333339333333
Ran Canetti and Ari Karchmer. Covert learning: How to learn with untrusted intermediary. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography 19th International Conference,
TCC 2021. Raleigh, NC. USA, November 8-11, 2021, Proceedings, Part III, volume 13044 of Lecture Notes in Computer Science, pages 1-31, Springer, 2021. 1601100.0077998---000--00090 //doi org/ 10 1007/ /978 3- 9030099456--00
2
Matthias C. Caro, Jens Eisert, Marcel Hinsche, Marios loannou, Alexander Niemne, and Ryan Sweke, Interactive proofs for verifying (quantum) learning and testing. CoRR, abs/2410.23369,, 2024a. doi N0011044850/ARXI2241002222
URL httttstt///.ooo... orgo 2...48850/arr... arXiv 2410. 23969
Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, and Ryan Sweke. Classical verification of quantum learning. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPles, pages 24:1-24:23. Schloss Dagstuhl Zentrrum für Informatik. 2024b. doi 100.2200LLPIICSSICSSSS. 2024.22 2024. 24
URL https: org/ 10. 20.00/2210/I.... ITCS
Dario Catalano and Dario Fiore. Vector commitments and their applications. Kaoru Kurosawa and Goichiro Hanaoka, editors, Public-Key Cryptography PKC 2013 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, February 26 March 1, 2013. Proceedings, volume 7778 of Lecture Notes in Computer Science, pages 55-72. Springer, 2013. 1071111..100077780--1- 642 36362-7
doi 10. 100100077977833462233336-1
URL http:://dbb..rrg//00000///////1/
5
Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, URL httptt/////oi. htt:///ii.or//// org/10. 1145/
pages 47-60. ACM, 2017. (4410..1145200533930555551111 3055399. 3055491
Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. CoRR, abs/1511.03777 1.0374,, 2015. URL http:///aaxii..rrra////111111
Lijie Chen, Jian Li, and Mingda Qiao. Towards instance optimal bounds for best arm identification. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 535-592. PMLR, 2017. http::ttt:///ee httt:://rroceeeingg mlr. .pres// v65/chenn7b..h html
Xi Chen and Xiaotic Deng. Settling the complexity of two-player Nash equilibrium. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA. Proceedings, pages 261-272. IEEE Computer Society, 2006. doi 109/FOSS 2006.69 URL
10. 1w1111000FFFC 2006.
Miranda Christ, Daniel Reichman, and Jonathan Shafer. Protocols for verifying smooth strategies in bandits and games. CoRR, abs/2507. 10567, 2025. doi 00010088550//AX81220001.666 URL
https://doi. cocddi.oorge org/10 48550/ 2507 105677
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing Nash equilibrium. Commun, ACM, 52(2):9-99, 2009. 2007 101.1114/5//4112884466655
URL https:///oi. org/10. 1145/1461928, 1461951
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, and Abhishek Shetty. Smooth Nash equilibria: Algorithms and complexity. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of L.Ples. pages 37:1-37:22. Schloss Dagstuhl Leibniz-Zentrun für Infor- matik, 2024. doi, doi 10044200/LPICCS/TCCC222.22 URL, htt.::tttt/:/ett ://dii 100/10 4230/LIPIcs ITCS. 37

---

Eyal Even-Dar Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi aumt bandit and markov decision processes. In Jyrki Kivinen and Robert H. Sloan, editors, Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, volume 2375 of Lecture Notes in Com- puter Science, pages 255 Springer, 2002. doi 000TT000007//-5444553333 18 -400075335-00-445------3--3-33
URL https
John Fearlley, Martin Gairing, Paul W. Goldberg, and Rahul Savani. Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16: 1305-1344, 2015, doi db1:100355//78992.286667 (0t.:/5555//2282 2886792
URL httph://pll........ acm. 0tg/000/110.6555/78997777
Aurelien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 998-1021 JMLR.org, 2016. URL http: http://prooceedings mlr. press/v49 garivier16a. html
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. doi: 007.1117/021180 18012 URL https
//doi.org/10. 110.001111/20299980 /0218012
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):27:1-27:64, 2015. doi|T0.1145/2699436 URL https
//doi.org/10. 1100001111/2299383
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPlcs, pages 41:1-41:19. Schloss Dagstuhl Leibniz-Zentrrum für Informatik, 2021. doi [0.42300LIICCS/TCS2200000 URL httpss://oii org 10. 4230/LIPIcS..../ ITCS. 2021
41
Mika Göös and Aviad Rubinstein. Near-optimal communication lower bounds for approximate Nash equilibria. SIAM J. Comput., 52(6) 2023. 101110.1337/99M122266 URL
https://doi. orreiii.rg/11.. 1137/19m1242069
Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean- Sébastien Coron, editors, Advances in Cryptology- EUROCRYPT 2016 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, volume 9666 of Lecture Notes in Computer Science. pages 305 326. Springer, 2016. 1t11//978-3-66--99888
11
URL https://doi org/ 10
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar. On the power of interactive proofs for learning. In Bojan Mohar, Igor Shinkar, and Ryan O' Donnelll editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1063-1170... ACM, 2024. doi IO. 011553668220.364977
URL htttps://dot wrg/oo..//11 11w.//111///100111/ 3649784
K wwan--Sung Jun, Lihong Li, Yuzhe Ma, and Xiaojin (Jerry) Zhu. Adversarial attacks on stochastic bandits. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 3644-6646660 2018. URL htRptttps///pooeedd// iew.eddiiinnnnuuussss.... cc/ cc/pappr/2018/ hwt.e/aaaaaaaaaaeaaaaeaaaaeaaaaa /tt///000000000255555aaeaaaaaaa. http://aaaatbbbb---bbtttttttttta
Zohar Shay Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings pages 1238-1246, JMI..org. org. 2013. httpttt:: ptttt:://proceedinggs mlr. .press/ saress/v8/// h2t//22///keee karnin13 html
12

---

Michael J. Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for near- optimal planning large markov decision processes. Mach. Learn., 49(2-3):193 208, 2002. doi 101792299177
URL httpsttts////o.
1023/A 1017932429737
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22 22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Shie Mannor and John N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. J. Mach. Learn. Res., 5:623-648, 2004a. URL httph://jjmnm..... org/ wwwpg//ggg///////oo////o/.../ra/ ppapers/voummete volume5/
mannor04b/manor0O4 pdf
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-arme armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-648, 2004b.
Saachi Mutreja and Jonathan Shafer. PAC verification of statistical algorithms. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 5021-5043. PMLR, 2023. URL http::t/ppoceeeeinnggge mlr press/v195/ mutrej a2wa. html
Aviad Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria. SIGecom Exch., 15(2):45-49, 2017. doi T0. 14755559155505555933355566 Ittps:/// org/
10. 10.1145/3355550 000155559999395666
3055596
Adi Shamir, IP = PSPACE. J. ACM, 39(4):869-877 1992. doi:10.1145/146685.118
URL
https://don http:///oooorg////// 10. 1145/146588 146585 146609
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of
algorithms in practice. Commun. ACM, 52(10);7--4,, 2009, 10.41.0011511555274.1557777 URL
https://doi. org/10. 10. 1111111151/14..1111 1562785
Richard S. Sutton and Andrew G. Barto. Reinforcement learning an introduction, 2nd Edition. MIT Press, 2018. http:t///wwww wwwp://wwwwlweeee.aaa... hwt.oppppacaiaaaaaaaaaa/oettttta
.ttll
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robust offline reinforcement learning. In Gustau Camps-Valll Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5757-5773, PMLR, 2022. URL htttt:::://oceeedinngge mlr. wttpe//iinnnnm...rer/s//ti/ press//v551/2hag2222 html
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper establishes the contributions and scope stated in the abstract
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We clearly elaborate on the assumptions we make in the paper
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide full proofs of all claims, either in the paper or the Supplementary
Material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper does not have experiments
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer:
[NA]
No code or data in the paper (other than pseudocode visible to everyone reading the paper)
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pp wwcppblicgguticcccccccceee.oo.pe /eeggudddsse/eebbbinninn ssiiisoliccyyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
No experiments in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:/ppp....aao..oooo/o/oo//taa
Answer: [Yes]
Justification:
We reviewed the NeurlPS code of ethics and made sure there are violations
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss possible benefits of verification of multi aumti-armed bandits. The discussion very theoretical and high-level
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No data or models in our paper
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We do not have code, data models in our purely theoretical paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do have new assets in the paper
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing in our paper
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No research including human subjects was done in our paper
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: Content in the paper is original and was created by the authors without resorting to LLMs (other than minor language edits)
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
20


Reviews:
[{"review_id": "Cc1jQbQozr", "reviewer": "Reviewer_qtLM", "summary": "This paper studies the problem of efficiently verifying the approximate optimality of strategies in multi-arm bandit and normal-form games under a smoothness constraint on the possible strategies. The paper considers $\\sigma$-smooth strategies which are a set of randomized strategies where no action gets selected with probability more than $\\sigma$. \n\nIn verification for MABs, instead of finding the optimal strategy, they consider the question that if a verifier is given a list of approximate rewards, can the verifier output a near optimal strategy or disprove that the given rewards are not approximately correct. The authors use the framework of interactive proof systems where a verifier interacts with an untrusted prover. They consider an oracle setting where the verifier and prover can both make queries to an oracle, and the goal is to find the approximate optimal strategy or reject the prover’s strategy by making sublinear in $n$ calls to the oracle.  $n$ is the number of possible arms in MAB, or the number of actions available to each player in normal-form games. \n \nTo achieve sublinear query complexities, protocols studied require $\\sigma n = o(n)$ which is motivated as a requirement that the strategies considered are “well spread” on the support size.\n\nThe authors construct a protocol where $\\varepsilon$-optimal $\\sigma$ smooth bandit strategies can be verified where the verifier makes $\\tilde O( \\frac {n \\sigma}{\\varepsilon^2})$ calls to the oracle. If $\\sigma n = o(n)$, then this is sublinear in $n$, which is lower the queries required to find the approximately optimal arm, i.e. $ \\Omega (n)$ queries. The authors also show a matching  $ \\Omega ( \\frac {n \\sigma}{\\varepsilon^2})$ lower bound for the number of queries required under the set of protocols considered. The authors then use SNARK and vector commitment (VC) techniques from cryptography to lower the communication required using cryptography so that prover only has to communicate only sublinear in $n$ bits to the prover for the prover to be able to the find the approximately optimal smooth strategy.\n\nFor normal-form games, they use similar idea to to construct a proof for showing that a given strategy profile is an approximate smooth NE or reject if it's not approximately smooth, but now the verifier requires  $\\tilde O( \\frac {n k \\sigma}{\\eta^2})$ where $\\eta$ is a slackness parameter.", "questions": "- Could you provide more intuition on when strategies are likely to be \"smooth\" in real-world scenarios other than the limited resource constraint example?\n- Are there any broader class of problems in where the smoothness holds or is violated that can guide practitioners on when to use these protocols?\n- Can you clarify the role of the slackness parameters and some intuitive discussion on why it’s needed for the game setting? Can you highlight the fundamental difference or challenge in adopting the results for the MAB case? Is the problem harder or is this a consequence of techniques?\n- Can we verify the protocol empirically at least in the MAB setting?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper introduces a novel problem, verifying strategy optimality over finding the optimal strategies in MAB and normal-form games.\n- The problem studied is well motivated, studying smooth strategies has been motivated by previous works as well. \n- The paper provides good theoretical foundations for the protocol provided. Under their setting, the protocol is able to accept or reject by making queries which are sublinear in $n$ and the authors provide a matching lower bound.\n- Results for improving communication efficiency in the interactive proof and obtaining the approximately optimal strategy in sublinear in $n$ communication. \n- Applications of these results for verifying approximate Nash equilibriums in games.\n\nWeakness:\n- Even though the requirements for  $\\sigma n = o(n)$ are motivated through some examples, a more-in depth discussion of its implications is missing. A discussion of where it might hold or not hold could strengthen the general applicability of these protocols.\n\n- The role of the slackness parameter is not well discussed in the paper. How should the slackness parameter be set with respect to $\\varepsilon$?\n\n- No empirical evidence for the claims.", "was_revised": true, "final_justification": "The authors have responded to my concerns. I am increasing the score to an accept.", "rebuttal": "Thank you for carefully reading and evaluating our paper and for providing constructive feedback.\n\nOn Smoothness\n==\n\n> Even though the requirements for $\\sigma n=o(n)$ are motivated through some examples, a more-in depth discussion of its implications is missing. A discussion of where it might hold or not hold could strengthen the general applicability of these protocols.\n\n> Are there any broader class of problems in where the smoothness holds or is violated that can guide practitioners on when to use these protocols?\n\n> Could you provide more intuition on when strategies are likely to be \"smooth\" in real-world scenarios other than the limited resource constraint example?\n\nYes, absolutely! \n\nAs you pointed out, one very general and common pattern that pops up in many real-world situations involves resource units with **bounded capacities** (what you called \"limited resources\"). These are scenarios where there is a system with many resource units, each of which can bear a limited load. For instance, one might want to assign jobs to computers in a data center, assign car traffic to various routes from point A to point B, assign containers to container ships, assign phone calls to agents in a call center, assign wireless communications to wave frequencies, etc. In each case, we want to assign each task or object to the best resource unit, but because each resource unit has only a limited capacity, the assignment will have to be smooth. In this sense, our setting is very broadly applicable. \n\nGoing beyond the bounded capacities scenario, another very important consideration is **robustness**. Even if one could assign all tasks to a single resource unit, that is typically not advisable — it is not a good idea to “put all our eggs in one basket”. Even if the entire monthly batch of iPhones to be delivered to the USA from the factory in China could in principle fit in one container ship, it would still be a much better idea to distribute the load between a number of different ships, in order to limit the damage in case something goes awry. In that sense, requiring that a strategy be smooth is a way to ensure robustness.\n\nSmoothness is also desirable in **adversarial settings**, because it makes the strategy harder to anticipate. For instance, a security company might want to assign its patrols to the properties where burglaries are most likely (or more accurately —  properties where the expected loss is highest). But if it concentrates all its patrols on just a few properties, then burglars can simply focus their crimes on other properties. Therefore, it might make sense for the security company to use a smooth strategy that assigns patrols at random to many different properties under its responsibility, while still prioritizing properties according to expected loss.\n\nLastly, smoothness also captures a certain sense of fairness or **equality**. In the foregoing example of a security company, if the company assigns all its patrols to a single house with the highest expected loss from burglary, that would be unfair towards the other home owners that pay for protection. On the other hand, if the company selects a perfectly smooth strategy, then it patrols all homes equally. In general, smoothness quantifies where the strategy falls on the spectrum between being fully equal and being fully unequal, with smoother strategies being more equal.\n\nOn Empirical Evaluation\n==\n\n> No empirical evidence for the claims. \n\nWhile implementation and evaluation are always important, we think it is reasonable for a theory paper focused on theoretical development like ours to not include an empirical section at least in the conference version. Please note that our paper is long (Full version is more than 40 pages) and is packed with new definitions that are already challenging to include within the 9 pages limit. There is no commonly agreed upon dataset such as imagenet or MNIST that allows for a simple evaluation of our protocol, and such an evaluation would likely need to consider both bandits and games making the paper significantly longer. Other influential theoretical papers in this area such as “the sample complexity of exploration in the multi-armed bandit problem” and “PAC Bounds for Multi-armed Bandit and Markov Decision Processes” do not include empirical evaluations as well. We think it is reasonable to provide such results for a journal version that is less space constrained. To be clear, we think implementing our protocols is certainly doable and cryptographic primitives used such as vector commitments and SNARKS have existing implementations that can be used towards this end, though this might be a big undertaking in practice. \n\n> Can we verify the protocol empirically at least in the MAB setting?\n\nYes, this is definitely doable, but it is out of scope for a theoretical paper like ours.\n\nOn Adopting to MAB\n==\n\n> Can you highlight the fundamental difference or challenge in adopting the results for the MAB case? Is the problem harder or is this a consequence of techniques?\n\nWe're not sure we understand this question. Could you please explain further? Our results are already for MAB (and games). Generally, we are not adopting existing results from some other setting to an MAB setting, so we don’t understand what you mean by “adopting the results for the MAB case”."}, {"review_id": "p7HnDNZ11I", "reviewer": "Reviewer_qUd4", "summary": "The problem studied in this paper is very interesting and useful. It is about to verify the correctness of the information provided by an external party. Ideally, we want to the number of queries to be sub-linear in the number of actions. They also consider the communication cost between the verifier and the prover.", "questions": "1. Here, since some parts of this work use bandit. My first question is, from which aspects, the proposed problem set-up needs to balance the classical exploitation-vs-exploration tradeoff. I do not see any discussion about this trade-off through the paper. If it does not need to balance these two aspects, why using bandit?\n\n2. For the definition of $\\sigma$-smoothness, for me, it seems to be counterintuitive. If we put all mass on a single action, it seems to be easier to learn than the case where we put even mass among actions. \n\n3. In line 63, a near-optimal strategy, the wording strategy means an algorithm or a distribution? Based on footnote 1, it seems it means a distribution? so why in bandit, it needs to find a near-optimal strategy, it means the found distribution is very close to the true reward distribution in the underlying bandit problem?\n\n4. Can you add some sketch about how to boost the constant probability ⅔ to $1-\\delta$? It seems to be non-trivial and I guess we need to pay an extra log factor right?\n\n5. For the bandit part, I feel that it is very close to the lower bound proof in bandit, but I am not sure how to connect them. So, can the authors explain more about the connection between your proposed approach and the exiting bandit lower bound?\n\n6. I am not in this field but why do we need communication between prover and verifier?  And why RL also needs it? My understanding is, after the query, verifier knows the truth. So, they do not need to communicate at all. Why verifier need to tell something to the prover?\n\n7. For the $\\epsilon$-Nash equilibrium part, I feel that it is very close to differential privacy. Is it connected? My intuition is they both need to bound the probability rations. \n\n8. For the corrupted bandit literature, I hope to see more discussions about the similarities and differences between corrupted bandit setting and the studied setting in this paper. \n\n9. Typos: in Line 63 and 126, it should be an MAB not a MAB.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "I am not an expert in the field of game theory; I provide my evaluation based on my own expertise in bandits. \n\nStrengths: the studied problem is very interesting; it is not a typical problem set-up in bandit literature. \n\nWeakness: some terminology are so confusing. If my understanding is right, for example, strategy and  policy here in this paper mean probability distribution, but in bandit/RL literature, it usually learning algorithms. Also, when I see VC, VC dimension hit my head. \n\nFor the presentation, I can follow most of the writings, but I suggest to move the formal problem set-up earlier. \n\nBox below has my detailed questions.", "was_revised": true, "final_justification": "This work is well written. I do not have any further comments.", "rebuttal": "Thank you for carefully reading and evaluating our paper and for providing constructive feedback.\n\nWeaknesses\n== \n\n> Some terminology are so confusing. If my understanding is right, for example, strategy and policy here in this paper mean probability distribution, but in bandit/RL literature, it usually learning algorithms. Also, when I see VC, VC dimension hit my head.\n\nYes, we can totally understand the confusion! In game theory, a strategy or policy is usually a distribution over actions (for instance, people use the terms “pure strategy” and “mixed strategy”). As you point out, in bandits and RL the terminology is different. Because our paper covers both bandits and games, we decided to choose one terminology (the game theory one) and employ it throughout the paper. \n\nTo reduce confusion, we will replace all appearances of “VC” in the text with the full phrase “vector commitment”.\n\nQuestions\n==\n\n> 1. Here, since some parts of this work use bandit. My first question is, from which aspects, the proposed problem set-up needs to balance the classical exploitation-vs-exploration tradeoff. I do not see any discussion about this trade-off through the paper. If it does not need to balance these two aspects, why using bandit?\n\nIt is true that algorithms for bandits usually require balancing exploration vs. exploitation. In our paper, we are essentially approaching this problem from a slightly different perspective, asking, “what happens if we delegate the exploration to an untrusted party?” The prover claims they did all the exploration for us, and they are giving us a distribution of arms to pull that allegedly achieves (approximately) the best exploitation possible. Seeing as the prover is untrusted, can this information actually be useful? How many arm pulls does the prover save us compared to doing all the exploration ourselves?\n\n> 2. For the definition of sigma-smoothness, for me, it seems to be counterintuitive. If we put all mass on a single action, it seems to be easier to learn than the case where we put even mass among actions.\n\nYou are correct that it is easier to find a strategy with high utility vs. finding a strategy with equally high utility that also satisfies an additional requirement of being smooth. Still, smoothness can be very desirable in some cases, e.g., because it makes the strategy more robust (“not putting all our eggs in one basket”), or because each arm can only be pulled a certain amount of times (each Uber driver can only do a certain number of rides a day), etc. An interesting point in our paper is that it is a lot easier to _verify_ optimality for smooth policies vs. general (non-smooth) policies.\n\n\n> 3. In line 63, a near-optimal strategy, the wording strategy means an algorithm or a distribution? Based on footnote 1, it seems it means a distribution? so why in bandit, it needs to find a near-optimal strategy, it means the found distribution is very close to the true reward distribution in the underlying bandit problem?\n\nIn this paper, a policy and a strategy always mean the same thing: a probability distribution over the possible actions. This is consistent throughout the paper. See Definition 5.1. One way to find a near-optimal smooth strategy is to find a vector that is very close to the true utilities vector of the bandit, and then use Algorithm 2 (l. 836 in the appendix) to compute a strategy. \n\n> 4. Can you add some sketch about how to boost the constant probability ⅔ to $1-\\delta$? It seems to be non-trivial and I guess we need to pay an extra log factor right?\n\nDefinitely, and you are correct about the log factor. Given a protocol (V,P) with soundness and completeness ⅔ as in Def. 5.4, we can amplify this to $1-\\delta$ as follows. Execute the protocol $k=O(\\log(1/\\delta))$ times. If V rejects more than $k/2$ times, then reject. Otherwise, for each (of the at least $k/2$) policies output by V, run the policy for $t=O(\\log(k)/\\epsilon^2)$ test steps. Finally, output the policy that obtained the highest utility during the test steps. Overall, if V makes $m$ oracle calls, then the amplified verifier uses $O(\\log(1/\\delta)*m + \\log\\log(1/\\delta)/\\epsilon^2)$ oracle calls.\n\n> 5. For the bandit part, I feel that it is very close to the lower bound proof in bandit, but I am not sure how to connect them. So, can the authors explain more about the connection between your proposed approach and the exiting bandit lower bound?\n\nDo you mean that the lower bound in Claim 2 (l. 644 in the appendix) is similar to the lower bound for learning bandits in Lemma 3 of Even-Dar et al. (2002)? That is true, as we point out in l. 864 of the appendix. In both cases, there is a reduction from the coin problem (Claim 10). The difference is that  Even-Dar et al. show a reduction from the coin problem to an algorithm that finds a good bandit arm. In our cases, we show a reduction from the coin problem to an interactive proof system with a prover and verifier that finds a _smooth_ bandit strategy.\n\n> 6. I am not in this field but why do we need communication between prover and verifier? And why RL also needs it? My understanding is, after the query, verifier knows the truth. So, they do not need to communicate at all. Why verifier need to tell something to the prover?\n\nYou are correct that communication from the verifier to the prover is not strictly necessary, and indeed, in Thm 5.5 we present a protocol that consists of a single message from the prover to the verifier (the verifier does not send any messages). However, an interesting observation that we explore in this paper, is that the total number of bits of communication exchanged between the two parties can be significantly reduced if we allow the verifier to send messages to the prover as well. \nYou can think of these messages sent by the verifier as *questions* that the prover must answer. The fact that the *verifier* chooses the questions is very useful, as if the prover chose the questions itself, it could always choose questions it can answer correctly.\n\nOur protocol for Thm 5.6 uses a number of communication bits that is sublinear in the number of actions n. The basic idea is to use a cryptographic commitment scheme: the prover sends a short commitment to the full proof, the verifier chooses some specific parts of the proof to inspect, and then the prover sends only those parts, and finally the verifier can check that what was sent matches the original commitment.\n\n> 7. For the Nash equilibrium part, I feel that it is very close to differential privacy. Is it connected? My intuition is they both need to bound the probability rations.\n\nUnfortunately we don’t quite see a connection to DP here. Perhaps if you elaborate further, things will click for us.\n\n> 8. For the corrupted bandit literature, I hope to see more discussions about the similarities and differences between corrupted bandit setting and the studied setting in this paper.\n\nExcellent question! In the corrupted bandit setting, a malicious adversary can change the information the learner gets when pulling an arm and thereby influence the learner’s estimate of the expectation of the arms. \nIn our setting, we introduce a prover that may be adversarially controlled; however, the adversary has no control over the information that the verifier receives from the bandit itself. The prover should be thought of as a purported expert giving (possibly faulty) recommendations about the bandit. The learner (verifier) has access to these untrusted recommendations, as well as untampered-with access to the bandit. \nOur setting is more generous to the verifier than in the corrupted bandit setting: the verifier can always ignore the prover, in which case it is in the standard (non-corrupted) bandit setting. But the verifier can do better by not ignoring the prover.\n\n> 9. Typos: in Line 63 and 126, it should be an MAB not a MAB.\n\nThanks for the catch! We will fix."}, {"review_id": "i40eMd8uSF", "reviewer": "Reviewer_H6h7", "summary": "This paper introduces interactive proof protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games, focusing on \"smooth\" strategies that do not concentrate too much probability mass on any single action. The authors develop verification protocols with sublinear query complexity O(σn/ε²) for σ-smooth strategies, where σ bounds the maximum probability on any action. Key contributions include: (1) efficient MAB verification protocols requiring fewer queries than learning, (2) cryptographic optimizations using vector commitments and SNARKs to achieve sublinear communication, (3) matching lower bounds proving near-optimality, and (4) extension to verifying smooth Nash equilibria in games with exponential improvement over computing equilibria without help. The work bridges interactive proof systems, machine learning verification, and game theory.", "questions": "Mentioned in weaknesses.", "limitations": "The authors adequately acknowledge several important limitations: focus on offline verification, smoothness assumptions, and cryptographic overhead.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1 This work addresses a genuinely unexplored intersection of interactive proofs, multi-armed bandits, and game theory. The application of verification paradigms to bandit problems represents a significant theoretical advance, moving beyond traditional learning-centric approaches.\n2 The paper provides tight upper and lower bounds for verification complexity, demonstrating O(σn/ε²) sufficiency and Ω(σn/ε²) necessity. The proof that verification requires strictly fewer queries than learning (Ω(n) for learning vs. O(σn/ε²) for verification when σ = o(1)) establishes clear theoretical separation.\n3 The integration of vector commitments and SNARKs to achieve O(λ·nσlog³(1/ε)/ε) communication complexity is technically sophisticated and represents novel application of cryptographic tools to ML verification.\n\nWeaknesses:\n1 While theoretically elegant, the gap between the theoretical protocols and practical implementations using existing SNARK and vector commitment libraries is unclear, and some empirical validation would strengthen the contribution.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reading and evaluating our paper and for providing constructive feedback.\n\nStrengths\n==\n\n> This work addresses a genuinely unexplored intersection of interactive proofs, multi-armed bandits, and game theory. The application of verification paradigms to bandit problems represents a significant theoretical advance, moving beyond traditional learning-centric approaches.\n\nThank you! This sentence sums up in a great way why we are excited about this work. \n\nWeaknesses\n==\n\n> While theoretically elegant, the gap between the theoretical protocols and practical implementations using existing SNARK and vector commitment libraries is unclear, and some empirical validation would strengthen the contribution.\n\nWhile implementation and evaluation are always important, we think it is reasonable for a theory paper focused on theoretical development like ours to not include an empirical section at least in the conference version. Please note that our paper is long (Full version is more than 40 pages) and is packed with new definitions that are already challenging to include within the 9 pages limit. There is no commonly agreed upon dataset such as imagenet or MNIST that allows for a simple evaluation of our protocol, and such an evaluation would likely need to consider both bandits and games making the paper significantly longer. Other influential theoretical papers in this area such as “the sample complexity of exploration in the multi-armed bandit problem” and “PAC Bounds for Multi-armed Bandit and Markov Decision Processes” do not include empirical evaluations as well. We think it is reasonable to provide such results for a journal version that is less space constrained. To be clear, we think implementing our protocols is certainly doable and cryptographic primitives used such as vector commitments and SNARKs have existing implementations that can be used towards this end, though this might be a big undertaking in practice. \n\nIndeed implementing SNAKRs and Vector Commitment is not immediate. However, please note it has been used in dozens of applied papers and has been implemented many times."}, {"review_id": "fJgH3WU749", "reviewer": "Reviewer_zq6z", "summary": "The authors study the problem of checking the PAC optimality of a strategy in a multi-armed bandit or whether it is a Nash equilibrium in a normal-form game. In a bandit setting for instance, given an environment from which rewards from arms can be sampled, a prover first proposes a strategy based on the rewards it observed, passes that strategy to a verifier, which can also interacts with the environment to check the quality of the strategy. The strategy is accepted by the verifier if it is nearly-optimal with high probability, and rejected otherwise. This paper focuses on smooth bandit/player strategies, where the probability mass is not concentrated on a single point. The authors propose a protocol which first makes the prover uniformly sample arms a fixed number of times, and makes the verifier split the reward interval [0,1] into bins of exponentially increasing length, select at random a pre-specified number of arms depending on the desired approximation rate and smoothness, and sample each of these arms a pre-specified number of times. If the deviation between the expected reward observed by the verifier and the expected reward provided by the prover is too large, then the verifier rejects the corresponding strategy. This protocol is extended to a case where low prover-verifier communication cost is important, and to the normal-form games. The authors also prove lower bounds on the number of queries to the environment needed to check the PAC optimality of a strategy/whether the strategy is a Nash equilibrium with high confidence.", "questions": "My main concerns relate to the assumptions made for the theoretical results from this paper (which is why I gave 1 for the quality), and the incurring limitations and handling of maliciousness from the prover (significance score).\n\n(1) Can you list all the assumptions needed in your theoretical results, based on the aforementioned weaknesses?\n\n(2) Can you discuss the limitations of all the assumptions needed in your theoretical results and for real-life applications, based on the aforementioned weaknesses?\n\n(3) How should the parameters $\\eta$ (slackness) and $\\lambda$ be chosen?\n\n(4) How can the prover be malicious in your setting? What kind of actions can it undertake (e.g., additive modifications of the empirical expected rewards sent to the verifier)?\n\n(5) Can you describe the technical issue for normal-form games, which led you to add the slackness parameter to this setting?", "limitations": "No. The authors did not include a paragraph nor specific sentences describing the limitations of their assumptions (e.g., on the boundedness of the distributions, on the existence of approximately optimal sigma-smooth strategies) and of the scope of their results (e.g., consequences on real-life applications of the smoothness constraint, restrictive setting for Nash equilibria).", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 1, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- Quality: The proofs for the quality of the “vanilla” protocol for the bandit setting (section C.2 in Appendix), of the algorithm converting empirical expected rewards into a bandit strategy (Algorithm 2) and the lower bound on the number of queries in a bandit setting (C.1) seem correct.\n- Clarity: The idea of a “proof idea” section is nice (but should perhaps be more concise). The authors made a good effort to contextualize their research, justify the setting by real-life applications, and present bounds in the literature. Providing an example in Lines 87-90 of verification is a good idea (but the use of Hoeffding’s inequality should be made clearer).\n- Significance: The problem of verifying a strategy, especially in a setting where the prover can be malicious, is an interesting problem.\n- Originality: Trying to extend a protocol for bandit algorithms to detecting approximate Nash equilibria is an interesting idea, and the resort to interactive proofs in a MAB setting is new to me.\n\n**Weaknesses:**\n- Quality: The assumption of bounded reward distributions (and the fact that it is a restrictive setting in a MAB setting) is not clearly mentioned (the notation $\\Delta([0, 1])$ is contradictory with the fact that $\\Delta$ was defined only for discrete sets in Line 281). The actual list of assumptions for the results (see Limitations) is not clear from the main text.\nThe proof for low-communication protocol is hard to understand without the cryptography section, which is mentioned in the main text but not present in Appendix. \nThe fact that in a normal-form game, all other players’ strategies should all be the same (Line 54) is also a strong assumption to me. These limitations are not properly discussed in the paper nor in Appendix. \nIn the field of fixed-confidence Best Arm Identification (Lines 231-244), Theorem 1 from [1] is not mentioned, while it is a central result for this problem. Moreover, the allocation vector $\\omega$ is connected to the strategy being verified in this paper. So I think this result should be discussed in the paper.\n\n[1] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998–1027. PMLR\n\n- Clarity: It is difficult to understand the exact setting and the interaction between verifier / prover / oracle up until reading the Appendix (I did not understand that the verifier had direct access to the raw observations from the oracle, for instance). Perhaps a figure or a small paragraph/pseudocode would help. The paper is unbalanced, with perhaps too large of an introduction / contributions paragraph, and little for the actual contributions and discussion. Avoiding bullet items, which can take a lot of space, would help I think.\n- Significance: I feel that the paper is a bit oversold on the potential maliciousness of the prover, since, in both protocols, the prover can only return the empirical expected rewards it observed. There is no constraint on the adversarial budget of the prover (unless I misunderstood something).\nThe choice of the various parameters $\\lambda$, $\\eta$, $\\epsilon$ and $\\sigma$ is not discussed, especially as I think the choice of $\\epsilon$ and $\\sigma$ has a large impact on the usefulness of the proposed protocols. Indeed, consider the following bandit instance with two Bernouilli arms: utility is (0.9, 0.1), consider $\\sigma = 0.7$. Optimal utility is achieved with strategy $\\pi=(1, 0)$ with a value of $0.9$. Best $\\sigma$-smooth strategy is $\\pi(\\sigma) = (0.7, 0.3)$ with a value of $0.66$. That is, no $\\sigma$-smooth epsilon-optimal strategy exists for $\\epsilon<30%$ (which is quite large in practice). So is the condition on smoothness still useful in that case for real-life applications, and is it restrictive for theoretical results, as perhaps only non-satisfying (i.e., with large $\\epsilon$) $\\sigma$-smooth solutions can be accepted by the verifier? For instance, the existence of a “good”  smooth strategy is an assumption for Theorem A.6 in Appendix (Line 733). \n- Originality: The proofs do not seem technically hard nor novel, as they result from the application of a well-known concentration inequality and mostly the boundedness of the distributions. A technical hurdle for normal-form games, requiring the introduction of a slackness parameter, is mentioned in the main text, but is unclear to me when checking the Appendix. The authors write that “The application of cryptography to RL is, to the best of our knowledge, uncommon.” (Line 109). However, it has been done for federated multi-armed bandits [1-2]. The question of reducing the communication cost has been studied also quite extensively in federated and for collaborative bandits for the best arm identification in fixed-confidence [3-4].\n\n[1] Ciucanu, Radu, et al. \"SAMBA: A generic framework for secure federated multi-armed bandits.\" Journal of Artificial Intelligence Research 73 (2022): 737-765.\n\n[2] Ciucanu, Radu, et al. \"Secure outsourcing of multi-armed bandits.\" 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 2020.\n\n[3] Kota, Srinivas Reddy, P. N. Karthik, and Vincent YF Tan. \"Almost cost-free communication in federated best arm identification.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 7. 2023.\n\n[4] Réda, Clémence, Sattar Vakili, and Emilie Kaufmann. \"Near-optimal collaborative learning in bandits.\" Advances in Neural Information Processing Systems 35 (2022): 14183-14195.", "was_revised": true, "final_justification": "A lot of things (contributions, assumptions, settings) were unclear to me from this paper, especially the main text, and I do not believe (for now) that it is ready for publication. There are remaining confusions (perhaps only misunderstandings on my side) so for now I increase my score to 2 on account on some of my concerns being cleared by the authors.", "rebuttal": "Thank you for carefully reading and evaluating our paper and for providing constructive feedback.\n\nWe categorized your main concerns into those pertaining to our assumptions, the significance of our results, and technical novelty. We have significant clarifications for all of these points, which we will happily add to the paper. These clarifications also address Questions (1), (2), and (4). We respond separately to Questions (3) and (5) at the end.\n\nAssumptions:\n==\n\nIt appears that most concerns come from misunderstandings and a notational issue, which we are happy to clarify in the paper. The one exception is the assumption of bounded reward distributions, addressed below.\n\n> The assumption of bounded reward distributions (and the fact that it is a restrictive setting in a MAB\n\nWe are happy to add this assumption to the limitations section of the paper. Nevertheless, the bounded setting is very common and used in important and influential papers such as Even-Dar, Mannor, and Mansour as well as Mannor and Tsitsiklis (both cited in the paper). As our paper introduces a new framework, we think it is reasonable to make this assumption.\n\n> The authors did not include a paragraph nor specific sentences describing the limitations of their assumptions… e.g., the existence of approximately optimal sigma-smooth strategies\n\nBy definition, approximately optimal sigma-smooth strategies for bandits always exist (see def A.3). An epsilon-optimal sigma-smooth strategy is defined to be any strategy whose value is within epsilon of the value of the *optimal sigma-smooth strategy*; in particular, the optimal sigma-smooth strategy is an epsilon-optimal smooth strategy for any epsilon. Therefore, in your example, the best sigma-smooth strategy (0.7, 0.3) is *itself* an $\\epsilon$-optimal sigma-smooth strategy for *every* $\\epsilon > 0$. Do you have further questions about this definition? It is crucial to our paper, so we are very happy to help clarify both here and in the paper itself.\n\nFor games, our protocol allows a prover to convince a verifier that a given strategy profile is an approximately optimal sigma-smooth Nash equilibrium; if no such equilibrium exists, soundness of our protocol implies that the verifier rejects. We make no assumptions.\n\n> The notation Delta[0,1] is contradictory with the fact that Delta was defined only for discrete sets in line 281.\n\nThank you for pointing this out. We will fix this inconsistency and define Delta for continuous sets as well. We write Delta[0,1] to mean a probability distribution over the continuous interval [0,1].\n\n>The fact that in a normal-form game, all other players’ strategies should all be the same (Line 54) is also a strong assumption to me\n\nWe do not make any assumptions about the other players’ strategies. In our setting, the prover is given *any* strategy profile and wishes to convince the verifier that it is an approximately-optimal sigma-smooth Nash equilibrium. We are happy to clarify this.\n\nIn summary, and answering **Question (1)**: our only assumption is that the rewards of the bandit or game are bounded in [0,1].\n\nAnswering **Question (2)**: Our protocol is useful in scenarios where smooth strategies are desirable, and rewards are bounded. We mention several of these in the intro (lines 119-125). As mentioned in line 122, smoothness is required when the frequency with which each arm can be utilized does not grow as the number of arms grows. Furthermore, in many practical examples, bounded rewards are realistic as, e.g. in the ride-hailing service, a ride never incurs a payment of more than say $300. We are happy to list more examples. \n\nSignificance\n==\n\n> I feel that the paper is a bit oversold on the potential maliciousness of the prover, since, in both protocols, the prover can only return the empirical expected rewards it observed. There is no constraint on the adversarial budget of the prover (unless I misunderstood something).\n\nAnswering **Question (4)** as well: We allow the malicious prover to behave *arbitrarily*. We do not impose a constraint on the adversarial budget of the prover because it is unconstrained: soundness implies that no malicious prover, even one returning arbitrarily far purported arm values, can convince the verifier to accept a non-optimal strategy with high probability. Perhaps the confusion arises from the fact that in the protocols, we define the behavior of the honest prover. This is in order to achieve completeness: *if* the prover follows this behavior and the given strategy is approximately optimal, then the verifier accepts with high probability.\n\nTechnical Novelty\n==\n\n>The proofs do not seem technically hard nor novel\n\nThis is a paper presenting a conceptual development: introducing the machinery of interactive proofs to bandits and games. While the core contribution of the paper is conceptual rather than technical, the proofs are not immediate. For example, consider the verifier query complexity’s (optimal) dependence on 1/epsilon^2 in Protocol 1. The verifier wishes to check that the total difference between the purported arm values and true values is not too great. One way to do so would be to check that “most arms are very close”: choose roughly n * sigma/epsilon arms, estimate their expected values within epsilon (taking 1/epsilon^2 pulls per chosen arm), and compare the estimates to the purported values. This requires n * sigma/epsilon^3 arm pulls. However, this is more work than is necessary: some arms’ purported values can be farther than epsilon, as long as not too many of them are. We leverage this observation to reduce this dependence to n*sigma/epsilon^2, using a bucketing approach. Its proof is not obvious, and spans several pages in Appendix C.2.\n\nWe acknowledge that the proof we included in the body of the submission (Theorem 5.6) is the most straightforward of those in the paper; this choice was intentional given the page limit.\n\n>However, it has been done for federated multi-armed bandits [1-2]. … The question of reducing the communication cost has been studied also quite extensively in federated and for collaborative bandits for the best arm identification. \n\nThank you for pointing out these other works. We agree that our comment about our usage of cryptography was overstated. We will soften this claim and add a discussion of these papers. We do note that while they are worth discussing, these papers are in a different setting and do not have direct implications for our results.\n\nQuestions (3) and (5):\n==\n**Necessity of the slackness parameter.** Imagine an alternative definition of an interactive proof for verifying epsilon-approximate smooth Nash equilibria, with no slackness parameter: For any epsilon-approximate smooth equilibrium, the prover must be able to cause the verifier to accept; for any strategy profile that is strictly more than epsilon-far from a smooth equilibrium, the verifier must reject. This would require the verifier to distinguish (with the help of the prover) between epsilon-approximate equilibria and (epsilon + delta)-approximate equilibria *for all delta > 0*. This is impossible if the prover and verifier together make a finite number of queries to the game oracle, as it is impossible to compute the *exact* expected payoff of a strategy. Therefore, a slackness parameter is required to allow some approximation error. We now guarantee that the verifier should accept epsilon-approx optimal strategy profiles but reject anything more than (epsilon + eta)-far from optimal.\nThe slackness parameter does not arise in our main setting, where the prover can choose the policy it wishes to prove approximate optimality of. Then, it can choose its own slack. e.g., by choosing a (2epsilon/3)-optimal policy it is effectively allowed (epsilon/3) slack.\n\n**Setting the slackness parameter.** Eta and epsilon together determine how much error the verifier is willing to accept, and how sensitive the other players are to small changes in their utility. \nSuppose the players in your game have “alpha-bounded precision” in that if they can’t improve their utility by more than alpha, they will keep their current strategy. This is true in many practical scenarios; for example, in our ride-hailing example a driver will not cancel a ride to make $\\alpha=1$ dollar more. We can divide this $\\alpha$ between $\\epsilon$ and $\\eta$. If we outsource finding an $\\epsilon$-approximate equilibrium to an expert, $\\epsilon$ determines how well the expert must do. $\\eta$ determines how accurate the verifier’s estimates must be. Therefore, we can set $\\epsilon$ and $\\eta$ to trade off different complexities depending on our application.\n\n**Setting the security parameter.** In cryptography, the security parameter determines the amount of work that it requires to break the guarantees of the protocol. At a very high level (oversimplifying a bit), it takes roughly 2^lambda time to break a protocol. For cryptography applications, where security must be very strong, lambda is typically taken to be ~128. In practice one could afford to choose a lower lambda (perhaps 50) for bandit verification protocols.\n\nMisc. comments\n==\n>In the field of fixed-confidence Best Arm Identification (Lines 231-244), Theorem 1 from [1] is not mentioned, while it is a central result for this problem.\n\nThe theorem from the aforementioned paper provides precise (non asymptotic) lower (and upper) bounds for best arm identification for MAB instances where the distribution depends on a single real parameter and where there is a distinct arm of maximum expected reward.. Please note that we are interested in asymptotic lower bounds and we cite such lower bounds (Even Dar et al., Mannor and Tsitsiklis). We are happy to cite [1] in the paper. \n\n> Moreover, the allocation vector \\omega is connected to the strategy being verified in this paper.\n\nWe do not follow this comment. What is the “allocation vector,” and how is it “connected” to the strategy being verified?"}]

Author rebuttal:

Meta-review: This paper develops interactive-proof protocols for verifying the approximate optimality of σ-smooth strategies in multi-armed bandits and normal-form games using sublinear oracle queries. The key message in the paper is that verification can be more efficient than learning under smooth policies in both single and multi-agent settings. Moreover, the use of crypto-related techniques to reduce communication cost is also interesting. 

Even though some reviewer has some negative comments (mainly on the presentation), after reading this paper myself, I think the criticisms are a little bit harsh.  To me, I find the newly introduced problem setting and framework very interesting, which might inspire many follow-up works in this direction. Thus, I recommend the acceptance. Meanwhile, I would strongly recommend that the authors take time to reorganize the structure and improve the presentation in the next version.
Decision: Accept (poster)