acceptodds
Under review as a conference paper at ICLR 2027

Identification and Off-Policy Evaluation in Markov Games with Adaptive Opponents

Abstract

Deploying a policy in a multi-agent system can change how the other agents behave. Off-policy evaluation should therefore measure the policy against the opponent response induced by deployment, not against an average opponent in the log. We show that this induced-response value is unidentified without observable response structure and cannot be estimated when the target lacks support on relevant state-joint-action triples or state-response pairs. We introduce a finite response-state model in which the response at stage depends only on earlier response states. The induced path is therefore obtained by forward recursion, not by solving a simultaneous fixed point. Given analyst-specified response maps , our polynomial-time method reconstructs response labels for the logging policies, estimates an opponent-response kernel, recovers the response to each undeployed target in one forward pass, and applies pessimistic off-policy evaluation on the target-reachable support. When overlap is incomplete, we give outer confidence intervals under partial identification for completions that share a response path. We also bound the value error caused by response-model misspecification. Together, these results distinguish structural identification from response recovery and statistical uncertainty.

Primary area:
reinforcement learning
Keywords:
Off-policy evaluation, offline reinforcement learning, Markov games, adaptive opponents, structural identification, partial identification, pessimistic evaluation.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_bNsMOpenReview ↗
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 π→μπ\pi \rightarrow \mu^{\pi}, there are two adaptive games with the same offline law and different Vcf(π)V_{cf}(\pi), 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

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 11, it selects bh=1b_h=1 exactly when πh(1∣s)≥1/2\pi_h(1\mid s)\ge 1/2. This is a threshold on the learner occupancy. Prop. J.1 also allows a specified descriptor χ(π)\chi(\pi) 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 tt for action 00 and the learner's action aa for action 11. The best response switches at x=tx=t, where xx is the learner's probability of action 11. With t=0.4t=0.4 or 0.60.6, the loggers at x=1/4x=1/4 and 3/43/4 induce the same responses 00 and 11 in both games and cover every joint action. With the same learner reward r(a,b)=br(a,b)=b, the logged data have the same law because opponent payoffs are unobserved. At the target x=1/2x=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.

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: Ph(s′=1∣s,a,b)=0.10+0.35a+0.35bP_h(s'=1\mid s,a,b)=0.10+0.35a+0.35b. Each period, the rival picks one pricing regime z∈{0,1}z\in\{0,1\} for all of its stores (the tier of Section 3), and its price at a store follows g(⋅∣s,z)g(\cdot\mid s,z).

A profit-maximizing rival. Suppose the rival's gain per store from regime 1 over regime 0 is κ (1{a=high}−12)\kappa\,(\mathbf 1\{a=\mathrm{high}\}-\tfrac12) with κ>0\kappa>0. 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

κ(∑sphπ(s) πh(high∣s)−12)=κ(qh−12).\kappa\Big(\sum_s p^\pi_h(s)\,\pi_h(\mathrm{high}\mid s)-\tfrac12\Big)=\kappa\big(q_h-\tfrac12\big).

The rival's profit-maximizing regime in each period is therefore zh=1{qh≥12}z_h=\mathbf 1\{q_h\ge\tfrac12\}. This is exactly the E8 rule and an instance of Definition 3.1.

Why the state dynamics matter. The share qhq_h depends on the inventory mix phπp^\pi_h, 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 php_h, 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 zz 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 zz 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.

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

This paper studies off-policy evaluation in Markov games where deploying a policy changes the opponent’s behavior. The authors first show that evaluating a policy against the response it induces requires additional assumptions beyond ordinary coverage. They then introduce a finite response-state model and propose a method that recovers the opponent’s response and evaluates the target policy from offline data. Theoretical guarantees and synthetic experiments are provided.

Critical strengths

The problem is well-motivated, as accounting for the opponent’s response to a deployed policy is practically important in multi-agent systems. The distinction between state-joint-action coverage and state-response coverage is also useful for understanding what information is needed to evaluate undeployed policies.

Critical weaknesses

My main concern is that several central terms and symbols are not sufficiently defined, making the paper difficult to follow. For example, “state-response” is repeatedly used from the abstract onward to describe a central coverage requirement, but I could not find an explicit definition of the term. The reader must infer its meaning from the subsequent model and equations. Similarly, νlog\nu_{\mathrm{log}} and μlog\mu^{\mathrm{log}} are used without explicitly stating the distributions they represent. Other terms, such as “policy-labeled,” are introduced before their meaning is explained. Since these concepts are essential to understanding the problem and the theoretical results, I believe that clearer definitions and explanations are necessary.

Additionally, I believe that the organization of the paper needs substantial improvement. The introduction provides a numerical example of the problem, but it is unclear how it leads to the subsequent contributions. Moreover, Section 3 mixes the problem setting and response structure with results on triangularity, forward recursion, and identification, making it unclear what the main message of the section is. More generally, while paragraph headings are frequently used, the connections between the paragraphs are often unclear. It would be helpful to explain why each topic is introduced and how it relates to the preceding discussion, rather than leaving these connections to the reader.

Questions for authors

My main concerns and questions are outlined in the Critical Weaknesses section.

1 comment

Thank you for pointing out where the notation and organization made the argument hard to follow.

Definitions and notation. Section3 defines νlog\nu_{\mathrm{log}} as the distribution used to assign a learner policy to an episode. Its label records the complete assigned policy, and the offline law is the joint population distribution of that label and the recorded trajectory. Def. 3.1 specifies how the learner occupancies determine a response regime zz. A state-response pair (s,z)(s,z) combines a physical state with that regime, and g(⋅∣s,z)g(\cdot\mid s,z) is the opponent action distribution there. Visiting ss in a different regime can supply data on the game without revealing this response row. §7 defines the pooled baseline as μpool,h(b∣s)=Plog(bh=b∣sh=s)\mu_{\mathrm{pool},h}(b\mid s)=\mathbb{P}_{\mathrm{log}}(b_h=b\mid s_h=s). This replaces the earlier μlog\mu^{\mathrm{log}} notation for the baseline.

What the calculation establishes. We moved the numerical calculation from the introduction to App. H.9. It uses one state and two equally likely loggers with probabilities 1/41/4 and 3/43/4 of taking a2a_2. The opponent chooses b1b_1 below a threshold of 1/21/2 and b2b_2 otherwise. The only nonzero reward is one at (a2,b1)(a_2,b_1). The target always takes a2a_2, induces b2b_2, and has value zero. The state-only pooled opponent chooses b1b_1 half the time, giving value 1/21/2 with the same joint reward table. Pooling rewards conditional on a2a_2 gives 1/41/4, since a2a_2 occurs three times as often under the logger that induces b2b_2. Both quantities differ from the identified target value. Thm. 4.2 separately shows that with an unrestricted response rule, two games can have the same logged distribution and different target values even with full joint-action support.

Order of the argument. The introduction now motivates the deployment decision before stating the identification question. Section 3 is devoted to the data and the model. Section 4 uses that model to derive the forward recursion and identify the rows needed along the target path. Section 5 explains how to recover those rows and the response path from a finite sample. §6 then treats incomplete support and response misspecification. The opening of each of §§4–6 states its purpose and connects it to the preceding analysis. The held-out experiment in Section 7 gives a case where the required response rows come from several logging policies and no logger generates the entire target response path.

We hope these changes address your comments satisfactorily and make the connection between the definitions, calculation, and results easier to follow.

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

This paper studies a two-player game where an agent (learner) is deployed in the presence of an adaptive player, adapting its behavior to the committed policy of the learner. From a dataset of labeled logging trajectories and unknown response states, this work aims to extract the best policy among a given set of target policies.

Under an assumed finite response-state model, the authors develop and analyze an algorithm that with high probability recovers an epsilon-suboptimal target policy. This epsilon vanishes at a rate 1/sqrt{n} in the number of sampled episodes n provided a large enough target margin.

The bounds are then empirically illustrated in a synthetic environment.

Critical strengths
  • The problem of evaluating a target policy against an adaptive player/opponent is interesting and relevant. The relevance of the work versus a naive pooling estimator is well motivated in the introduction.
  • Assumptions and limitations are stated explicitly.
Critical weaknesses

Motivation and setting:

  • The finite response-state model is not motivated enough, making it hard to judge the significance of the contributions. This model is at the heart of the work, providing the key simplifications that the subsequent results rely on. It would be very insightful to have a concrete application of this model close to its definition.
  • After the modeling assumption, the analysis boils down to a margin argument for label recovery and standard pessimism. Lemma 3.2 (triangularity, page 3) holds by construction since the maps are defined on occupancy prefixes. This makes the final contribution look incremental. Can the authors specify which steps of the analysis are technically non-standard and how they would approach extending beyond the simplistic model of Definition 3.1?

Theory:

  • The local margins are never formally defined in the main text. They are only informally introduced on page 5. Given their importance in the analysis, they should receive a formal definition in the main text.
  • Proposition 5.2 page 8 is a standard performance-difference bound. As noted by the authors, the interesting part which is the uniform l1 error cannot be estimated from the logs (“This guarantee requires an externally justified induced-response discrepancy.”). The result therefore adds little in practice.
  • Similarly, the Bernstein remark on Page 8 doesn’t seem directly useful. The paper does not establish such a concentration argument. This is correctly stated by the authors (“This is a conditional refinement, not a claim that a data-dependent value function automatically satisfies an empirical Bernstein bound.”). Without a proof of such concentration it does not seem useful to the reader.

Additional writing issues:

  • In the paragraph following Proposition 4.2 (page 6), Delta_h is used but not defined. It is only defined later in the proof sketch (page 7).
  • The introduction (page 1) refers to C_cf and C_sr. These are forward references that cannot be understood, as they are only defined on page 4 after the problem formulation. A similar thing happens with page 2 referring to a triangular response operator, which is unclear to the reader.
  • v_0 is not defined in Corollary 4.4 (page 7). The corollary also seems superfluous, as it restates the pessimism already given by Theorem 4.3 (page 6).
  • On page 9, the comment “positive action probabilities provide a route to coverage” is imprecise. Using the paper’s words on page 4, “a logging policy can visit every state-joint-action triple while visiting a state only under the wrong response label, making C_cf finite and C_sr infinite”, hence state-response coverage cannot be guaranteed.
Questions for authors
  • For Proposition 4.1 on page 5, why use SA instead of S? A remark mentions “The displayed condition conservatively uses SA.” Relatedly, isn’t the second term redundant with the first term in terms of sample complexity? If I understand correctly, this would be the case because the margin γlog\gamma_{\text{log}} is upper bounded by twice the horizon H (if finite).
4 comments

Thank you for your comments on the sample-size bound, the response model, and the contribution of the proof.

Margin and logging-label bound. Both observations about Prop. 5.2 are correct. For a fixed logging policy, d~h(s,a)=p~h(s)πh(a∣s)\widetilde d_h(s,a)=\widetilde p_h(s)\pi_h(a\mid s). Since ∑aπh(a∣s)=1\sum_a\pi_h(a\mid s)=1, the error ∥d~h−dh∥1\lVert\widetilde d_h-d_h\rVert_1 equals ∥p~h−ph∥1\lVert\widetilde p_h-p_h\rVert_1. Concentration is over SS states, so the revised bound uses SS in place of SASA. Def. 5.1 measures the distance to a label-changing prefix with the same policy factorization. The prefix domain has diameter at most 2h2h at stage hh, so any finite logging margin is at most 2H2H. With γˉlog=min⁡(γlog,2H)\bar\gamma_{\mathrm{log}}=\min(\gamma_{\mathrm{log}},2H), the sufficient condition is n≳H2(S+log⁡(MH/δ))/(νmin⁡γˉlog2)n\gtrsim H^2(S+\log(MH/\delta))/(\nu_{\min}\bar\gamma_{\mathrm{log}}^2). The margin term absorbs the separate cohort-count term up to constants. If all logging margins are infinite, the labels are constant on their admissible domains and can be computed directly. For known threshold rules with Lipschitz summary bounds, App. K uses count-based confidence sets to certify a label when every compatible prefix gives the same threshold decisions. The procedure abstains if that check fails.

Which steps are specific to this problem. The forward order follows from the timing (Lemma 4.1), as you noted, and the final Bellman step uses standard pessimistic evaluation. Three steps connect them. First, we prove concentration for counts formed with the true response labels. On the recovery event of Prop. 5.2, the reconstructed counts equal the true-label counts, so the same episodes can be used for both tasks. Second, Prop. 5.3 and App. C weight transition and response errors by the true target occupancy. Plug-in mass outside that support is accounted for by the current occupancy error Δh\Delta_h. The proof therefore needs no coverage of alternative response paths. Third, Lemma C.2 controls the primitive rows on one event shared by all targets, removing the target-menu logarithm. Its separate treatment of rare rows uses bounded errors and clipped bonuses, removing the global minimum positive logging-mass requirement. Thm. G.4 also gives a worst-case expected selection regret lower bound of order (H−1)min⁡(1,∣Z∣/n)(H-1)\min(1,\sqrt{\lvert\mathcal{Z}\rvert/n}) in a subclass with joint-action concentrability at most two.

Motivation, scope, and coverage. Beside Def. 3.1, §3 now describes a controlled pricing protocol. Two automated agents set prices simultaneously after the platform announces a tier computed from the learner's high-price probability. The model assumes a shared rival price distribution at a given inventory and tier across deployments. Logging must reach the state-tier pairs and joint-action cells used by the target. Positive action probabilities alone cannot ensure this. §8 gives a sufficient design condition using a logger that shares the target's response path and assigns at least a fixed fraction of the target's action probabilities at every state and stage. Props. J.1 and J.2 extend the model to a specified policy descriptor and observed finite memory, with the corresponding coverage requirements.

Sensitivity and presentation. Prop. 6.2 uses a standard performance-difference bound. If an external argument bounds the uniform opponent-policy discrepancy by ε\varepsilon in ℓ1\ell_1, subtracting min⁡(H,H(H+1)ε/4)\min(H,H(H+1)\varepsilon/4) from a valid model-based lower bound preserves validity. The archive alone cannot bound that discrepancy for an undeployed target. The conditional Bernstein discussion is in App. H (Prop. H.1), because the paper does not establish the required variance envelopes for this estimator. We define Δh\Delta_h where it first enters the recovery argument, introduce the coverage ratios in §4, and fold the selection corollary into the discussion of Thm. 5.4. There v0v_0 is a prespecified return floor. On the simultaneous confidence event, a selected policy whose lower bound clears v0v_0 also clears that floor in value.

We hope the revised bound and the clearer account of the model and proof address your comments satisfactorily.

I thank the authors for their answer and the revised version of the paper. The revision addresses the specific points I raised related to e.g. the dimension in Proposition 5.2, the formal definition of the local margin, terms like Δh\Delta_h and the coverage remark on page 9.

On the motivation and scope I appreciate the addition of a motivating example in the paper. However, in this example, the margins are infinite since the learner's high-price probabilities are constant across states, making the tiers depend on the policy only ("If the learner’s high-price probability is state-independent, the platform can compute a tier by thresholding the assigned policy’s probability at each stage.", p.3). Hence, the subsequent theory only applies trivially to this case (e.g. eq. (7) becomes vacuous), while label and path recovery (Propositions 5.2 and 5.3) matter only with finite margins.

Motivation is therefore still missing for the finite-margin case where the responding agent needs to know the state-action distribution of the hh first steps for every step hh to determine its response zhπz^{\pi}_h. What kind of applications would be covered by this?

Presentation A significant portion of the paper appears to have been modified in the revision, but it remains dense and the motivation from the peculiar setup is not given in the introduction.

Thank you for acknowledging the earlier corrections and for identifying the remaining gap in motivation. You are correct: if the high-price probability is state-independent, the tier is determined by the known policy alone, and the corresponding margin is infinite. That special case does not illustrate the statistical label- and path-recovery problem. We will replace it as the main motivating example.

1. A state-dependent application and its information requirements

Consider a chain that deploys one inventory-dependent pricing policy across its stores. A platform observes the current inventory mix and announces the expected share of high prices under the assigned policy. A programmed rival selects a pricing mode from this aggregate, then draws its store-level prices conditional on local inventory and the mode. The aggregate is computed before the current prices are drawn; it is not the realized frequency of current high-price actions.

Specifically, the announced aggregate is

q^h=1K∑k=1Kπh(ahigh∣Sh(k)).\widehat{q}_h = \frac{1}{K} \sum_{k=1}^{K} \pi_h(a_{\mathrm{high}} \mid S_h^{(k)}).

A configured threshold selects the mode, for example,

z^h=1q^h≥1/2.\widehat{z}_h = \mathbf{1}\\{\widehat{q}_h \ge 1/2\\}.

The rival therefore needs only an announced scalar or its tier, not the complete state-action distribution of every preceding step. The notation ϕh(d1:h)\phi_h(d_{1:h}) allows general prefix dependence, but includes this simpler current-aggregate rule.

Crucially, earlier prices affect later inventories. When the pricing probabilities vary across inventory states, the aggregate induced by a new policy depends on its evolving inventory distribution and hence on the unknown dynamics and earlier responses. Its modes cannot generally be read from the policy alone.

This is a configured aggregate-feedback application, rather than a claim about unrestricted rational competitors. Threshold-based admission controllers provide a related motivation: their operating settings can change with aggregate usage or congestion indicators, as in the broadcast access-control mechanism studied by Biagi et al. (2016). Our guarantees require the stated shared-kernel assumptions in addition to such a mechanism.

2. The existing E8 instance has positive, finite margins

The state-dependent instance in E8 already demonstrates the required recovery problem. Its target policy satisfies

π(ahigh∣s0)=0.90,π(ahigh∣s1)=0.05.\pi(a_{\mathrm{high}} \mid s_0) = 0.90, \qquad \pi(a_{\mathrm{high}} \mid s_1) = 0.05.

Thus,

qhπ=0.90−0.85phπ(s1),zhπ=1qhπ≥1/2.q_h^{\pi} = 0.90 - 0.85 p_h^{\pi}(s_1), \qquad z_h^{\pi} = \mathbf{1}\\{q_h^{\pi} \ge 1/2\\}.

Unlike the state-independent illustration, changing the inventory distribution can change the tier.

The corresponding margin is

γh(π)=2∣qhπ−1/2∣0.85.\gamma_h(\pi) = \frac{2|q_h^{\pi}-1/2|}{0.85}.

Consequently, the second- and third-stage margins are approximately 0.448820.44882 and 0.311730.31173, respectively—both positive and finite. The logger with statewise high-price probabilities (0.60,0.10)(0.60,0.10) also has a finite minimum margin, 0.215450.21545.

The target's complete response path is absent from the logging menu, whose paths are (0,0,0)(0,0,0), (1,1,1)(1,1,1), and (1,0,0)(1,0,0), although its required response rows are covered across the loggers. This is the case in which logging-label reconstruction and forward target recovery matter. The first target label is known from the initial distribution and policy; the nontrivial forward recovery begins at subsequent stages. We will bring this example and its finite-margin calculation into the main text.

3. Why the population model approximates finite-cohort feedback

Your question also motivates making the connection to finite, observable aggregates explicit. We can establish this connection under a precise condition: stores interact only through the shared response mode, with independent initial states and independent store-level action, reward, and transition randomness otherwise.

Let

d^h=p^h⊗πh,z^h=ϕh(d^1:h),\widehat{d}_h = \widehat{p}_h \otimes \pi_h, \qquad \widehat{z}_h = \phi_h(\widehat{d}_{1:h}),

where p^h\widehat{p}_h is the empirical inventory distribution and the mode is computed before current actions.

Couple the actual KK-store cohort with a reference cohort of KK independent trajectories generated under the population response path. Let

dhπ=phπ⊗πh.d_h^{\pi} = p_h^{\pi} \otimes \pi_h.

For the reference cohort, standard empirical-distribution concentration and a union bound over stages give, with probability at least 1−ε1-\varepsilon,

\max_{1 \le h \le H} \sum_{t=1}^{h} \left\\|\widehat{d}_t^{\mathrm{ref}} - d_t^{\pi}\right\\|_1 \le r_K(\varepsilon),

where, for a universal constant c>0c > 0,

rK(ε)=cHS+log⁡(H/ε)K.r_K(\varepsilon) = cH \sqrt{\frac{S+\log(H/\varepsilon)}{K}}.

Here, SS denotes the number of inventory states.

If

rK(ε)<min⁡1≤h≤Hγh(π),r_K(\varepsilon) < \min_{1 \le h \le H} \gamma_h(\pi),

every reference empirical prefix remains in the correct response cell. Inductively, the two cohorts then choose identical modes and have identical trajectories: agreement through one stage gives the same next inventories, and the margin preserves the next mode. Therefore,

TV⁡!(Lπ,Kcohort,(Lπpopulation)⊗K)≤ε.\operatorname{TV}\\!\left(\mathcal{L}_{\pi,K}^{\mathrm{cohort}}, (\mathcal{L}_{\pi}^{\mathrm{population}})^{\otimes K}\right) \le \varepsilon.

This gives finite margins an operational interpretation: they control how large a cohort must be for sampling fluctuations in its inventory mix to leave the population response path unchanged. The result is a quantitative approximation of the dependent cohort law, not an assertion that the cohort itself is independent.

For several logging cohorts, the coupling must be joint, and its failure probabilities add across cohorts. Conditional on exogenous cohort-policy assignments, the reference concentration argument uses the actual per-policy sample counts and coverage relative to that allocation. A reference failure bound δstat\delta_{\mathrm{stat}} then increases by at most ∑cεc\sum_c \varepsilon_c. The cohort-size condition must hold for each cohort; a large total sample size alone does not ensure it.

For a target cohort, assuming stage rewards lie in [0,1][0,1], the expected per-store return satisfies

∣VK(π)−Vcf(π)∣≤Hε.\left|V_K(\pi)-V_{\mathrm{cf}}(\pi)\right| \le H\varepsilon.

Accordingly, a population-value lower bound must be reduced by HεH\varepsilon to bound the finite-cohort expected value.

We will also distinguish the recording regimes. If every store's inventory and cohort identifier are archived, the realized cohort modes are directly reconstructible. Statistical label recovery is needed for sampled archives lacking those aggregates. In both cases, the margin controls agreement with the population path and the accuracy of the population-based target evaluation.

4. Finite-cohort check

We additionally evaluated E8 with modes computed from each cohort's realized inventory mix and the known policy, using 4,000 independent cohorts per policy and cohort size. The observed proportions preserving the complete population response path were:

Cohort size KKLogger (0.60,0.10)(0.60,0.10)Target (0.90,0.05)(0.90,0.05)
3086.5%96.6%
10098.6%99.9%
300100%100%

The logger's smallest scalar threshold slack is approximately 0.0540.054, compared with 0.1320.132 for the target. The other two loggers have policy-determined tiers and preserve their paths for every cohort realization. Here, 100% denotes observed success in the simulated trials, not a probability-one guarantee. These results illustrate the finite-margin mechanism; the coupling argument supplies its theoretical justification.

5. Presentation changes

We agree that this motivation should appear in the introduction. We will:

  • Open with the inventory-dependent multi-store example, explaining the observable aggregate, the rival's information, and why earlier responses affect later modes.
  • Replace the state-independent main illustration with the finite-margin E8 example and distinguish policy-only tiers as an easier special case.
  • Keep a concise finite-cohort statement and its assumptions in the main text, with the coupling proof and detailed probability accounting in the appendix.
  • Organize the method around logging-mode reconstruction, target-path recovery, and value evaluation; move the detailed sample-size derivations and robust recursion to the appendix while retaining the main theorem's assumptions.

Thank you again for your comments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.