- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies the problem of evaluating the performance of a target policy in a two-player Markov game using only offline data collected under a set of logging policies. The main challenge is that deploying a new policy may also change the opponent's behavior, resulting in trajectories that may not be represented in the offline dataset. The authors define a framework for the opponent, in which the response is a function of the distribution of learner's actions in previous steps, and estimate the off-policy performance under this framework.
Critical strengths
None
Critical weaknesses
1- In my opinion, the paper requires a thorough revision of its writing, as substantial portions of the it is completely incomprehensible. Many sections lack explanatory text to guide the reader about what is basically the objective of that section, and how the included theorems achieve that objective. Moreover, there are a lot of unexplained or vague terms, which makes understanding the results difficult. As an example, consider Theorem 3.3. It starts with the following sentence: "Without an observable restriction on , there are two adaptive games with the same offline law and different , giving constant minimax error." It is not clear what is meant by "offline law" or what is the definition of "observable restriction". There are many more examples such as this in the paper.
2- The entire analysis in the paper is conducted under the proposed response-state model. However, this model has a very limited practical applicability and does not capture the behavior of a rational opponent. More precisely, the model assumes that the opponent response is determined by the true distribution of the learner's actions in the past steps under the learner's known logging policy. This effectively implies that the opponent knows the learner's policy in each episode. However, for a rational opponent who is aware of the learner's policy, the decision making problem is basically reduced to an MDP, and the opponent would choose its actions by considering the future outcomes, not only the past. Also, the model does not account for the dynamic adaptation of the opponent to the specific play of the learner during an episode.
Questions for authors
Could the authors elaborate on the practical applicability of the finite response-state model in real Markov games and provide concrete examples of settings in which its assumptions are reasonable?
4 comments
I appreciate the effort the authors have put into addressing my concerns. However, neither of my concerns has been sufficiently resolved. The example the authors provide is a repeated game, while the paper's framing is about Markov games, where the actions affect next states.
Also, the revised submission is still extremely dense with frequent use of undefined terms and informal labels, which makes its readability significantly below a standard ICLR paper.
For these reasons, I would like to keep my original rating.
Thank you for the follow-up. We agree that the matching example in Section 3 has no state dynamics. The same structure appears in our main experiment, where both agents' actions change the next state.
The pricing game. In the main experiment (E8, Appendix I.3), each episode is one of the learner's stores. Its inventory evolves with both firms' prices: . Each period, the rival picks one pricing regime for all of its stores (the tier of Section 3), and its price at a store follows .
A profit-maximizing rival. Suppose the rival's gain per store from regime 1 over regime 0 is with . As in the matching game, it prefers the high-price regime where the learner prices high. Such payoffs exist for E8's price distributions, because the two regimes differ at every inventory level. Averaged over stores and over the learner's committed policy, the advantage of regime 1 is
The rival's profit-maximizing regime in each period is therefore . This is exactly the E8 rule and an instance of Definition 3.1.
Why the state dynamics matter. The share depends on the inventory mix , so the same policy can meet different regimes in different periods. One E8 logging policy prices high with probability 0.60 in one inventory state and 0.10 in the other.
- In period 1 all stores start in the first state, so its share is 0.60 and the rival chooses regime 1.
- Both firms' prices then move 59% of the stores to the second state. The share falls to 0.305 in period 2 and 0.446 in period 3, so against an unchanged policy the rival switches to regime 0.
- The regime in turn changes the rival's prices and therefore next period's inventory.
This feedback is why the target's regimes must be computed forward through the estimated dynamics (Lemma 4.1), and why the margins are finite.
Scope of rationality.
- Myopic rationality. This rival maximizes current-period profit. It is the myopically rational follower studied in general-sum Markov games by Zhong et al. (2023).
- Full rationality. When the opponent's action does not affect transitions (single-controller stochastic games; Parthasarathy & Raghavan, 1981), best-responding stage by stage is optimal over the whole horizon. An example is an attacker choosing the site with the highest expected payoff given patrol coverage , against a patrol whose next location depends only on its own moves. Its response is a fixed partition of coverage space into best-response regions. Coverage depends on the patrol's earlier moves and movement dynamics, so the margins are again finite.
- Planning opponents. When the opponent's action changes future states and it plans ahead, its response can depend on the learner's future policy (Appendix J). It is then covered only through a known policy descriptor (Proposition J.1).
- Unknown payoffs. Payoffs consistent with every logged response can still disagree about the target, so its value is not identified in general (the argument of Theorem 4.2).
Finite cohorts. The rival observes the inventory mix of finitely many stores. As shown in our reply to Reviewer dWsh, finite margins make the population model exact with high probability for moderate cohort sizes.
We will add this derivation and example to Section 3 and Appendix J.
We agree that the main text is still too dense and uses undefined terms and informal labels. The problems are specific, and so are the fixes.
One object, several names. The regime is called a response state, response label, regime label, regime and tier, and "label" also refers to the recorded policy. We will use regime for and assigned policy for the recorded policy throughout.
Informal labels. "Logger", "row", "physical rows", "completion" and the experiment codes E2, E4 and E8 appear without definition. "Compatible games" is also used in the introduction before it is defined.
- We will write "logging policy" and "conditional distribution" instead.
- We will define a compatible game (a game in the model class with the same offline law) at first use.
- Experiments will be described by what they test.
For example, the coverage paragraph of Section 4 currently reads: "The rollout needs reward and transition rows for every state and joint action reached by the target. It also needs an opponent-action row for each state and regime reached by the target." It will read: "To evaluate the target, we need the reward and next-state distributions at every state and pair of actions it reaches, and the opponent's action distribution at every state and regime it reaches."
Notation table. A half-page table in Section 3 will define every symbol and term used in the main text: offline law, assigned policy, regime, state–regime pair, target-reachable support, compatible game, local margin, and the two coverage coefficients.
Density. The robust recursion in Section 6 and the sample-size and certificate paragraphs in Section 5 will move to the appendix. The freed space will carry the pricing example through Sections 3–5. Each formal statement will be preceded by a one-sentence plain-language summary of what it says and why it is needed.
Thank you again for pressing on both points. We appreciate it if you can reconsider your score.
Thank you for your comments on the clarity of the identification result and on which opponents the model can describe.
What the positive result covers. Def. 3.1 applies when a specified rule maps the learner's population occupancies to a regime and the opponent action law is shared across deployments at each state and regime. §3 now gives a rational example. In a repeated one-state matching game, the opponent maximizes the probability of matching the learner's binary action at each stage, since neither action affects future states. With ties favoring action 1, it selects bh=1 exactly when πh(1∣s)≥1/2. This is a threshold on the learner occupancy. Prop. J.1 also allows a specified descriptor χ(π) of the complete learner policy to enter the response map. The descriptor can summarize future commitments, and the statistical bounds carry over under the same margin and coverage conditions for the resulting rule.
Forward-looking responses and identification. We agree that a rational opponent facing a committed policy generally solves a finite-horizon MDP. App. J gives two learner policies with the same first-stage occupancy and opposite future actions at the two states the opponent can choose between. Their first-stage best responses differ, which the original prefix map cannot represent. App. J also shows why rationality alone cannot identify a response from these logs. In a one-stage binary game, give the opponent payoff t for action 0 and the learner's action a for action 1. The best response switches at x=t, where x is the learner's probability of action 1. With t=0.4 or 0.6, the loggers at x=1/4 and 3/4 induce the same responses 0 and 1 in both games and cover every joint action. With the same learner reward r(a,b)=b, the logged data have the same law because opponent payoffs are unobserved. At the target x=1/2, the two responses and target values differ. This is the information limitation in Thm. 4.2.
Adaptation during play and a concrete setting. Prop. J.2 allows an observed finite history summary to be added to the state when it is sufficient for both the game dynamics and the opponent's response. Including the learner's previous action lets the opponent react to the actual preceding play. Coverage must then hold in the enlarged state, and both agents still move simultaneously at each stage. In the controlled pricing protocol in Section3, a state-independent high-price probability lets the platform compute the tier directly from the assigned policy. The rival sees the tier and its inventory before setting its price. In independently run episodes this announcement introduces no cross-episode dependence. A tier based on state-dependent population frequencies needs a reference distribution, and estimating a common tier from the same finite cohort can couple those episodes. The simulation in Section7 tests transfer under a documented rule and shared response distribution. A field use would need independent evidence for those assumptions.
The identification statement. §3 now defines the “offline law” as the joint distribution of the assigned learner policy and its recorded trajectory. We removed “observable restriction” from Thm. 4.2, whose first sentence now reads: “If the response to an undeployed policy can vary independently of all logged responses, two games can have the same offline law and different values for that policy, even with full joint-action support.” The positive part uses the specified rule and the covered response rows to link the target to the log.
We hope the revised statement, examples, and scope conditions address your comments satisfactorily.