Thank you for carefully reading and evaluating our paper and for providing constructive feedback.

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

Assumptions:

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

The assumption of bounded reward distributions (and the fact that it is a restrictive setting in a MAB

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

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

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

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

The notation Delta[0,1] is contradictory with the fact that Delta was defined only for discrete sets in line 281.

Thank 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].

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

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

In summary, and answering Question (1): our only assumption is that the rewards of the bandit or game are bounded in [0,1].

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

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

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

Technical Novelty

The proofs do not seem technically hard nor novel

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

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

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.

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

Questions (3) and (5):

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

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

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.

Misc. comments

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.

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

Moreover, the allocation vector \omega is connected to the strategy being verified in this paper.

We do not follow this comment. What is the “allocation vector,” and how is it “connected” to the strategy being verified?

Thank you very much for taking the time to write these informative and helpful comments! We truly appreciate this dialogue with you.

1. My concern is not about the choice of smooth strategies. As illustrated by the examples given, it might be well-motivated. My issue is with the choice of epsilon. It is an additive constant, which might be hard to assess in advance depending on the final goal. My point is that in real-life situations, a multiplicative epsilon (that is, a epsilon-good strategy has a value of epsilon times v* where v* is the optimal value). In the current setting, the verifier might accept strategies which value are extremely bad compared to the optimum, and there is no way to "compensate" by decreasing epsilon or adapt it to the observed data. Is there a way to extend your contributions to solve this issue?

Response: If we understand correctly, you are concerned that “In the current setting, the verifier might accept strategies which value are extremely bad compared to the optimum”, and you suggest that if we considered a multiplicative epsilon instead of an additive one, that would somehow solve this problem? If so, please understand that accepting strategies that are far from the best (nonsmooth) strategy is simply part of the price of smoothness: given that the protocol produces smooth strategies, such a gap is unavoidable, regardless of whether the approximation involves an additive epsilon or a multiplicative factor. Importantly, as we explained above, there are settings where the only strategies that matter are smooth strategies, and in those settings our protocols guarantee that the accepted strategy is epsilon close to the best benchmark strategy.

In practice, setting the value of epsilon can often be straightforward. For instance, suppose the optimal smooth strategy makes me a profit of \$10, and finding a nearly optimal smooth strategy would cost me \\$1, but there is an untrusted prover that offers to find a nearly optimal smooth strategy for me for \$0.5. Then I can set$\varepsilon$to be \\$0.4, so I accept a strategy that gives me at least $9.6 dollars of profit. This way, my total revenue would be at least 9.6-0.5 = 9.1, which is \$0.1 better than I would be without the prover.

Additionally, please note that an additive approximation of $\varepsilon$ is very standard in RL, bandits, PAC learning, etc. For example an additive error is used in the papers of Even Dar et al., and Mannor and Tsitisklis.

---

Mannor, S., & Tsitsiklis, J. N. (2004). The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun), 623-648.

Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.

2. Could you please provide the associated references? For instance, in the references in the paper related to bandits, the manipulation of rewards can be additive [1] or epsilon% of samples can be replaced [2]. Moreover, a clear pseudocode/paragraph is missing to understand the exact underlying setting and interaction between the prover and the verifier which is valid throughout the paper. I relied on the pseudocodes in Appendix but then it turns out that they are not representative of the setting.

Response: Of course! The definition of a “cheating” or “malicious” prover in an interactive proof system goes back to the seminal 1985 papers of Goldwasser, Micali, Rackoff [2], and Babai [3] (work for which a subset of the authors eventually received a Turing Award). The malicious prover can deviate arbitrarily from the protocol (and the prover is furthermore computationally unbounded, so it can evaluate any function including uncomputable functions).

This might sound strange at first, but it simply means that we want a strong guarantee that the verifier accepts statements only if they are true, and rejects false statements (with high probability) — regardless of what proof (or interactive transcript) the verifier is presented. Please note that this definition of unbounded prover is still the most widely used and accepted definition today more than 40 years after it has been introduced.

If you think of it, this might be familiar from the definition of the class $\mathsf{NP}$ (nondeterministic polynomial time). An $\mathsf{NP}$ verifier is given an instance and a witness string, and if the instance is not in the $\mathsf{NP}$ language, then for every witness string (no matter how the witness was constructed), the verifier must reject. In interactive proof systems, the “for every” quantifier is applied to the transcript of the interaction (the sequence of messages sent back and forth between prover and verifier), regardless of which prover was involved in the interaction.

There are of course many authoritative references for this classic definition in addition to [2], including:

• Chapter 8 (“Interactive Proofs”), Definition 8.3, in Arora & Barak [4].
• Section 10.4 (“Interactive proof systems”), Definition 10.28, in Sipser [5].
• For an online source, see the Wikipedia article on “Interactive proof system”, where it says, e.g., “no prover, however malicious …”.

---

[2] Goldwasser, S., Micali, S., & Rackoff, C. The knowledge complexity of interactive proof systems. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.

[3] László Babai. Trading group theory for randomness. Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM. 1985.

[4] Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.

[5] Sipser, M. (2013). Introduction to the Theory of Computation. Engage press.

Thank you for carefully reading and evaluating our paper and for providing constructive feedback.

Strengths

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.

Thank you! This sentence sums up in a great way why we are excited about this work.

Weaknesses

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.

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

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

Thank you for carefully reading and evaluating our paper and for providing constructive feedback.

Weaknesses

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.

Yes, 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.

To reduce confusion, we will replace all appearances of “VC” in the text with the full phrase “vector commitment”.

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?

It 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?

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.

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

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?

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

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?

Definitely, 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.

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?

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

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?

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

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

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.

Unfortunately we don’t quite see a connection to DP here. Perhaps if you elaborate further, things will click for us.

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.

Excellent 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. In 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. Our 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.

9. Typos: in Line 63 and 126, it should be an MAB not a MAB.

Thanks for the catch! We will fix.

Thank you for carefully reading and evaluating our paper and for providing constructive feedback.

On Smoothness

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.

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?

Could you provide more intuition on when strategies are likely to be "smooth" in real-world scenarios other than the limited resource constraint example?

Yes, absolutely!

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

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

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

Lastly, 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.

On Empirical Evaluation

No empirical evidence for the claims.

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

Can we verify the protocol empirically at least in the MAB setting?

Yes, this is definitely doable, but it is out of scope for a theoretical paper like ours.

On Adopting to MAB

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?

We'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”.

Thank you for these questions! Please see our answers below.

Is there a characterization of the optimal utility under the smoothness constraint vs when no such constraint is imposed?

Response: Great question! As noted by the other reviewer there are examples where the optimal smooth policy is worse by an arbitrary large multiplicative factor. We will add such an example to the paper.

Furthermore — yes! There is also a very simple characterization: Assume for simplicity that $\sigma = 1/k$ for some natural number $k$. Then it is easy to see that

Theorem: the price of smoothness is $u_1 - \frac{1}{k}\sum_{i=1}^k u_i$, where $u_1 \geq u_2 \geq u_3 \dots$ are the utilities of the arms sorted in decreasing order.

This is true simply because the optimal $\sigma$-smooth policy assigns equal weight of $1/k$ to the top $k$ arms, and therefore achieves utility which is the average of the top $k$ arms. We are very happy to add this characterization to the paper.

On empirical evidence, I understand that this is mainly a theoretical contribution and is considered out of scope, but I still believe some empirical evidence could have highlighted the practicality of the approach.”

Response: We agree. However, as the paper is very loaded with new definitions and concepts, and as there are no existing benchmarks or datasets for this framework, we think it is unfeasible to add empirical evaluation to the current paper (also taking into account the 9-page limit). The best solution in our mind is to state empirical evaluation explicitly as a direction for future research.

on adopting to MAB: My understanding is the MAB results are generalized/refined to obtain the results for the games. What are the main challenges in the proving the results for games and what aspect of the games setting makes it non trivial to "adopt" the MAB results to obtain the results for games?”

Response: The main challenge is that in the game setting, the prover has less choice over the strategy whose optimality they prove. This necessitates our introduction of a slackness parameter and our bandit protocol variant. We elaborate on this below. A second challenge is proving a stronger lower bound on the number of arm pulls of order $\Omega(k n \sigma)$, which requires new ideas that are not present in the bandit setting.

Slackness. In the bandit setting, the prover can choose which policy to send to the verifier, as long as it is smooth and $\varepsilon$-close to optimal. This allows the prover to choose a policy $\pi$ whose value is very close (say, within $\varepsilon/4$) to optimal, creating slackness for the verifier’s approximation of its value. That is, as long as the verifier estimates the value of $\pi$ within additive error $3\varepsilon/4$, it can still determine it is $\varepsilon$-optimal. On the other hand, in the game setting, the prover is given a strategy profile, and it must prove that this strategy profile is an $\varepsilon$-approximate equilibrium. We do so by reducing this task to many bandit protocols. However, for these induced bandits the resulting policy may be exactly $\varepsilon$-optimal. In this case, there is no slackness for the verifier: It must exactly learn this policy’s value in order to ensure it isn’t $(\varepsilon + \delta)$-far from optimal for some arbitrarily small delta. This is impossible with a finite number of queries to the game oracle. To resolve this, we introduce the slackness parameter and construct a bandit protocol variant that takes as input a fixed policy, rather than allowing the prover to choose its own policy.