The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Authors: Jiachen Hu
Rui Ai
Han Zhong
Xiaoyu Chen
Liwei Wang
Zhaoran Wang
Zhuoran Yang
Venue: ICML 2025 poster (2025)
Keywords: Strategic exploration
information asymmetry
knowledge transportability
Primary area: theory->reinforcement_learning_and_planning
TL;DR: This paper investigaetes sample-efficient online decision making under information asymmetry and knowledge transportability

Abstract: Information asymmetry is a pervasive feature of multi-agent systems, especially evident in economics and social sciences. In these settings, agents tailor their actions based on private information to maximize their rewards. These strategic behaviors often introduce complexities due to confounding variables. Simultaneously, knowledge transportability poses another significant challenge, arising from the difficulties of conducting experiments in target environments. It requires transferring knowledge from environments where empirical data is more readily available. Against these backdrops, this paper explores a fundamental question in online learning: Can we employ non-i.i.d. actions to learn about confounders even when requiring knowledge transfer? We present a sample-efficient algorithm designed to accurately identify system dynamics under information asymmetry and to navigate the challenges of knowledge transfer effectively in reinforcement learning, framed within an online strategic interaction model. Our method provably achieves learning of an $\epsilon$-optimal policy with a tight sample complexity of $\tilde{O}(1/\epsilon^2)$.

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Jiachen Hu
Rui Ai
Han Zhong² Xiaoyu Chen
Liwei Wang
Zhaoran Wang² Zhuoran Yang
Abstract
their diverse private information and their drive to maximize individual rewards, which give rise to what is termed in- formation asymmetry (Myerson, 1982; Gan et al., 2022a). Due to information asymmetry, the agents always strategi- cally choose their actions according to the predetermined and publicly known policy of the principal, while keep- ing their private information concealed from the principal's awareness. Here, we say agents are "strategical" because they will choose their strategic actions based on personal types and aim at maximum obtainment. A famous example in economics is the generalized principal-agent problem (Myerson, 1982), where a principal interacts with several myopic agents with private types and type-based strategic bidding.
Information asymmetry is pervasive feature of multi-agent systems, especially evident in eco- nomics and social sciences. In these settings, agents tailor their actions based on private infor- mation to maximize their rewards. These strategic behaviors often introduce complexities due to con- founding variables. Simultancously, knowledge transportability poses another significant chal- lenge, arising from the difficulties of conducting experiments in target environments. It requires transferring knowledge from environments where empirical data is more readily available. Against these backdrops. this paper explores a fundamen- tal question online learning: Can we employ non-i.i.d. actions learn about confounders even when requiring knowledge transfer? We present sample-efficient algorithm designed to accu- rately identify system dynamics under informa- tion asymmetry and to navigate the challenges of knowledge transfer effectively in reinforcement learning. framed within an online strategic interac- tion model. Our method provably achieves learn- ing of e-optimal policy with tight sample complexity of Ó(1/e).
On the other hand, it's also common and sometimes neces- sary for the learner in machine learning to generalize the knowledge from one domain to other related domains, which is often referred to as transfer learning (Zhuang et al., 2020). Similar phenomena have also been observed in casual infer- ence, which is known as knowledge transportability (Pearl & Bareinboim, 2011). Knowledge transportability stud- ies the problem of transferring information learned from experiments to different environments, where conducting active experiments is difficult or unfeasible but only pas- sive observations are allowed. Social problems, particularly medical issues, frequently involve instances of knowledge transportabiliity (Pearl & Bareinboim, 2011 I; Bareinboim Pearl, 2013). A motivating example effect of a treatment from one population (c.g.. experiments done in New York City) with a large number of samples to other populations where massive experiments might be not available (e.g., investigating the outcome of that treatment in Los Angeles).
1. Introduction
transfer the learned
Multi-agent systems are widely applied in reinforcement learning (RL) (Littman, 1994; Wang et al., 2019; Dubey & Pentland, 2021), economics (Brero et al., 2022), social science (Sabater& & Sierra, 2005), and robotics (Yan al., 2013). In systems like these, agents are characterized by
In this paper, we hope to theoretically study online decision- making under information asymmetry arising from the agents' side and knowledge transportability needed by the principal. Inspired by the generalized principal-agent prob- lem, we model scenario in which a principal sequentially interacts with a series of agents. Each agent, driven by short- term objectives, myopically maximizes her rewards based on her private information (Zhong et al., 2021). This model captures the dynamics of principal engaging with con-
'Shooo of Computer Science, Peking University Instiiutee for Data, Systems, and Society, Massachusetts Institute of Technol- ogy 'Center for Data Science, Peking University "National Key Laboratory of General Artificial Intelligence. School of Intelli- gence Science and Technology, Peking University Northwestern University " "Yale University. Correspondence to: Zhuoran Yang <zhuoran.yang yalc.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
tinuous flow of agents where their private types and actions directly affect the transition and the reward of the principal. The goal of the principal is to design policy to maximize his total rewards when interacting prospectively with spe- cific target population of agents, though the online data may come from a different population of agents thus knowledge transfer is necessary. As a result, we formalize this problem as an online strategic interaction model-a generalization of the strategic Markov decision process (MDP) similar to Yu et al. (2022), which studies offline setting. However, we must adaptively adjust our policy, i.e., time-varying, in an online learning setting to explore unknown environments. Therefore, our actions are not i..dd distributed, but are inter- dependent. Hence, the traditional concentration inequalities used in Yu al. (2022) do not apply to our case. This immediately raises a question:
In order to theoretically study reinforcement learning with information asymmetry and knowledge transporta- bility, we introduce the online strategic interaction model motivated by the strategic MDP (Yu et al., 2022), Our online strategic interaction model breaks the i.i.d. data condition and presents a scenario in which rein- forcement learning models can be learned using time- varying data. Technically, we propose a model-based algorithm in the general MDP setting which leverages the NPIV method to do causal identification of the underlying model.
We investigate the conditions under which our algo- rithm can provably learn a near-optimal policy. Us- ing O(1/e)) samples, the proposed model-based al- gorithm learns an c-optimal policy and show its dependency on the knowledge transportabilityy We de- fine a knowledge transfer multiplicative term Ct and use it as a measure of the hardness increased by trans- ferring knowledge (cf. Section 5).
Is it possible to learn model with confounders using non-i.id. actions and states?
There are two main challenges in our model in order to learn the optimal policy of the principal. The first one is the pres- ence of unobserved confounders- the agents' private types and private actions, which directly affect both the rewards and transition dynamics but are kept unobserved to the prin- cipal. The second is to transfer the learned information from online data to the target population of agents. prompts a second question:
1.1. Related Work
Our work is closely connected to several bodies of literature discussed below.
RL in economics. Many models problems extensively studied in economics have been combined with reinforce- ment learning. including Stackelberg game (Başar & Olsder, 1998; Zhong et al., 2021). Bayesian persuasion (Kamenica & Gentzkow, 2011; Gan et al., 2022b; Wu et al., 2022), mech- anism design (Gan et al., 2022a; Bernasconi et al., 2022), performative prediction (Mandal et al., 2022), etc. Different from those models, our work is natural extension of the generalized principal-agent problem to reinforcement leam- ing focusing on learning the optimal policy of the principal in the presence of information asymmetry and knowledge transportabilitty
Cun we design an approximately optimal algorithm if the target distribution and source distribution are different, and how does this difference affect the sample complexity?
Different from standard RL, the exploration needed here is more challenging because the heterogeneous agents can strategically manipulate their feedback to the principal, which affects the rewards and transitions.
We provide affirmative answers to both questions. To re- solve the challenges, we propose a model-based algorithm to learn a nearly optimal policy of the principal. Our algo- rithms leverage novel nonparametric instrumental variable (NPIV) method sparked by Angrist& & Imbens (1995); An- grist & Krueger (2001); Newey & Powell (2003); Ai & Chen (2003) with algorithmic instruments to establish causal iden- tification of the system in the presence of confounders. With such identification, we're re able to construct a high probability confidence set for the model or the value functions under the target domain transfer knowledge (Pan & Yang, 2009; Taylor& & Stone, 2009) using the method of moments. Our analysis shows that such model-based algorithm prov- ably learns ooptimal policy with only Ô(1/²)) samples which matches corresponding lower bounds up to logarith- mic terms.
Efficient exploration in RL. The exploration problem has been extensively studied in tabular MDPs (Auer et al., 2008; Azar et al., 2017; Dann et al., 2017: Jin et al., 2018; Dann et al., 2019; Zanette & Brunskill, 2019; Zhang et al., 2022), MDPs with linear function approximation (Yang & Wang, 2019; Jin et al., 2020; Yang & Wang, 2020; Cai et al., 2020; Ayoub et al., 2020; Zhou et al., 2021; Hu et al., 2021; Chen et al., 2021) and general function approximation (Russo & Van Roy, 2013; Jiang et al., 2017: Sun et al., 2019; Jin et al., 2021; Du et al., 2021). Apart from standard RL models, the strategic interaction model poses additional challenges due to, for instance, the strategic behaviors of agents caused by information asymmetry. Since the principal cannot observe agents' types, partially observed feedbacks bring higher uncertainty and more nuisance in algorithm design.
In summary, our contributions are two-fold:
2

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
RL with confounded Data. There is line of works study- ing reinforcement learning in the presence of confounded data (Chen & Zhang, 2021; Wang et al., 2021; Liao et al.,
generality, we assume he can observe 8 directly. Then he takes an action on according to the past states and actions, receives a reward Th RR as)) and transits to the next state $/+11 ~ P- 8h, ax).
2021; Shi et al., 2021; Bennett et al., 2021; Bennett & Kallus, 2021; Wang et al., 2022; Lu et al., 2022; Yu et al., 2022). The studies of Chen & Zhang (2021); Liao et al. (2021); Yu et al. (2022) also use the instrumental variables to do causal identification. Among them. Yu et al. (2022) is most related to this work, which studied strategic MDPs in the offline setting. In contrast, we study the online strategic interaction model together with knowledge transfer, a generalization of their model with a break of i..d. assumption, and distribu- tion shift. We provide an elaborate summary of the novelty in this work beyond Yu et al. (2022) and standard RL in Appendix B.2.
We consider the time-inhomogeneous Markov policy class II in this work. A policy ग = { E II maps each 8h to A(A) at step h. The value function V S - RR of policy и at step h conditioned on s/. is defined as
rr Sh s].
The goal is to learn an optimal policy n" with a highest cumulative rewards, viz,
n = arg max V (81).
xEIl
The principal-agent problem and instrumental variable model. The principal-agent problem well-known in eco- nomics (Myerson, 1982; Guruganesh et al., 2021; Zhang & Conitzer, 2021; Gan et al., 2022a), which features the strate- gic interactions between a principal and an agent with pri- vate type and private action. The challenges in the principal- agent problem are known as "moral hazard" (incomplete information about actions) and "adverse selection" (incom- plete information about types), which are both present in our work. The instrumental variable model has been extensively studied in economics (Angrist& & Imbens, 1995; Angrist & Krueger, 2001; Ai & Chen, 2003; Newey & Powell, 2003; Blundell et al., 2007; Chen & Pouzo, 2012; Chen & Qi, 2022), with applications in (statistical) machine learning (Harris et al., 2022) and reinforcement learning (Chen & Zhang. 2021; Liao et al., 2021; Yu et al., 2022). As an appli- cation of the instrumental variable model, we use the non- parametric instrumental variable model to build conditional moment equations and methods of moments to identify the underlying model.
3. The Online Strategic Interaction Model
The online strategic interaction model formalizes the se- quential strategic interactions of principal and H agents, where each agent possesses different private type sam- pled from a prior distribution.? 2 To elaborate further, at each step h E [H] = {1, HJ. an agent with private type 4, arrives and chooses a strategic action by that maximizes her own payoff. The principal needs to dynamically adjust his strategy actively engage in exploration, with the goal of learning an approximately optimal policy as quickly as possible. This prior distribution represents the population from which the online data is collected, which may be dif- ferent from the target population of agents, underscoring the necessity of knowledge transfer. We also call the prior dis- tribution as the source distribution P (P%) 1H km Starting
at fixed state $1, the interactions happen as follows (see Figure I for a more intuitive understanding):
For the h-thh agent, the principal transits to state sn and then takes an action an according to his strategy.
2. Preliminaries
The agent's private type tn is sampled from the unknown source population Ps- Based on it, the myopic agent strategically takes arg max, 12, (sh, ah L,, 6) to maximize her own re- ward R Note that t, and b, are both unobserved by the principal (Maskin & Riley, 1984).
We use Markov decision processes to depict the standard online interaction models involved in this paper, which can be summarized as (S,A, P. R, H. $1). ).& S and A denote the state space and action space, respectively. In the meanwhile, P P= (- 8, / and R = [s H) are the transition dynamics and reward functions, which are both unknown. H is the time horizon while 81 denotes the initial state.
action by
After the agent takes her action, the principal re- ceives a manipulated feedback en ~ Fu(: | 8h, ah, In, bn) from the agent according to her pri- vate information. Denote Fx(- |
For each episode, player interacts with the model starting from state i for H steps. When the player reaches state 8n. he receives an observation indicating Sn. So, without loss of
8h, an, (x) der F. | Sh, an, tn arg max, R (5h, an. tn. b)). then en ~ Fa(- 8h, ah, L.).
We assume the initial state is fixed state for simplicity. It's straightforward extend it to the case where 81 is sampled from fixed initial distribution.
PIt can also model the interaction of the principal and a single agent for H steps, who has different aspect of personal type drawn from a prior distribution at each step.
3

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Finally, the principal receives a reward Th Ri (Sa; (a (a)+ Eh. where Ri is an unknown function and En is assumed to be unobserved endogenous zero-mean noise (i.e., confounded with the private type ln referring to Appendix C). The principal transits to the next state #h+1 ~ (- 5h, Ohe, 64) according to an unknown function P% Similarly, we could also al- low the stochastic transition of $1+1 to be endogenous or confounded with t. Then the principal starts the interaction with the next agent.
via an observable term ey- However, the feedback eh is observed that it only conveys very limited information of the private type. In reality, the noise term Eλ may include the unobserved confounder in the reward that is not measured even when intervening with the feedback en. Please see the next section for some examples for further explanations.
Example 3.1 (Contract design). The sharcholders of a com- pany aim to maximize the stock price Sn2 and related re- turns. At each step h, the company decides whether to replace the CEO and what her compensation should be de- noted by an. CEOs can be either diligent or lazy, namely, ty E (Diligent, Lazy). }. Different types of CEOs will choose to exert different levels of effort by and whether a CEO is hardworking affects some hidden factors, e.g., the morale of the company's 's employees. Shareholders cannot observe the CEO's effort directly; they can only observe the opera- tional status of the company es. At time h, the shareholders' returns are influenced by several factors: the stock price and the operational status of the company which determine dividends, the CEO's salary, and employee morale (which may affect turnover rates). The first two terms constitute Ri, (sh; an, en) while the last unobserved term forms Çx- This explains the source of confounders and ends up with re- ward rh = (s ah En. The market can observe the company's 's stock price, financial statements, and operational condition at moment h, and these observations influence the stock price at /a + 1, saying Sh+1 ~ P 8h, Ok es) through self-fulflling expectation (Hamilton & Whiteman, 1985).
3.1. Motivation
Next, we discuss the motivation for designing the online strategic interaction model and use two real-world examples of the existence of confounders to digest this setting. More details can be found in Appendix C.
As mentioned in the introduction, the main motivation to study the online strategic interaction model is under- stand the strategy design of multi-agent strategic interaction (e.g., the generalized principal-agent model) in sequential deciisionmmakin setting, where both problems are common in reality. To better align this model with the real world, we incorporate several generalizations including the distri- bution shift of the agent population, the extensively large state space, and the endogenous noise in our model. Each of these generalizations greatly enhances the expressive power of our model in the sense that
Without distribution shift (i.c., the knowledge trans- portability), the model reduces single-agent RL, which is somehow not hard to compute near-optimal policies. The distribution shift condition initiates many challenges studied in the paper such as the confounding issue and the knowledge transfer.
Intuitively, this model enables agents to strategically ma- nipulate rewards of the principal and state transitions via their private information through their feedback en, which is more challenging than classic RL. The introduction of endogenous variables greatly enhances the generality of our model but also raises more challenges to designing ef- ficient algorithms. We provide more details of the model and the motivation, as well as more motivating examples in Appendix C. We use M (P*) to denote the online strate- gic interaction model under the source distribution and let p' = {P H be the target population of agents. We close off this section by providing an application scenario of knowledge transfer.
A large state space is ubiquitous in complex real-world problems. Our analysis characterizes the impact of problem size growth on the sample complexity of our algorithms, for instance, through the Eluder dimension.
Many practical applications have endogenous noises while existing work only assumes exogenous noise. In real-world problems, the principal is typically a company or an organization, and the agents are clients, employees, etc. The state 84 is usually the conditions of the company, and the rewards are the profits of the company over an agent, which has a deep connection to the private type of the agents (e.g., the personality, the health conditions). Thus, the distribution of the rewards is largely correlated to the private type. If the noises are exogenous variables, this correlation will be realized solely by the feedback e,. That is to say, the private type must influence the reward distribution
Example 3.2 (Experimental design.). With the rapid de- velopment of Large Language Models (LLMs), integrating LLMs into experimental design (Kumar al., 2023), such as A/B testing, has become a new trend. Compared to the high costs associated with using human samples for experiments, the cost of using LLMs is essentially zero. However, LLMS exhibit significant differences from humans in many as- pects. For example, in addressing an optimization problem, LLMs operate with complete rationality, whereas humans sometimes possess only bounded rationality (Simon, 1990;

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Transits to Sh+1
1. state Sn and action an
Principal
Agent chooses bn
2. type En.
Nature
receives Th
4. feedback en
Figure 1. Timeline of the interaction, Th and 81+11 (blue) influenced by observable 8he ah eb (red) and unobservable (green). We use numbers to indicate the sequence of events.
Conlisk, 1996). Therefore, experiment designers need to combine known human characteristics say Ph with experi- mental data derived from LLM features say 7s to develop optimal mechanisms tailored for human agents.
because En is zero-mean noise. Therefore, conclude that
EM-( (ra. Sh, En, B -Pi Pi Pa (188s9nn))) [Pn 8h, anl
(sh, an);
3.2. Planning the Online Strategic Interaction Model
Since we are trying to design model-basee algorithms, we introduce the planning algorithm the online strategic inter- action model in this section. If we are given the underlying rewards [Ri and transitions {= we can con- struct aggregated model with respect target type distribution pt, i... assuming the random type is sampled from Pt.
and analogously the transition of .M" (Pt) is also identical to (- sh, a.).
Now suffices to learn the optimal policy म of Mr. Since the aggregated model is an episodic MDP, its optimal policy is Markov policy, which justifies the previous definition of IT. Denote the value function of any policy on MM as V Ag say policy is e-optimal if
Define the aggregated model MM = (S, R. P P*, under the target distribution as
2
V M
M
R1 (Sh, an) def Euppy en R..( RR (Sh, ans e)]
3.3. Notation Guide
(3.1)
We use df, (.:s)) (resp. di (.:::)) to denote the joint dis- tribution of sh. an: en for policy under model M (P*) (resp. M (P))).) Sometimes
PR Sh, ax) del EemPy Flllbonan)) (P Sh, ah, c)]
also marginalize over en and use d% (-.-) (resp. d ((,))) denote the marginal distribution of 8h, on on (D*))) (resp. M*(P')). For any value function gh+1 S + R and transition dy- namics Pa(- S/s Ohs eh), we use Phgh+1 (Sh, ah. ex) def E. s' Ps) 8h, Cp) to denote the expectation of gh+11 under Pn.. For any function space X with function x² E X, define the translated space - x= {x x" x E X). A comprehensive table of notation, covering both the main body and the appendix, is provided in Appendix A.
(3.2)
It is known that the reward and transition dynamics in the target model MP(P)) is equivalent to M We provide brief explanation here and defer the details to Appendix C.
Given any (5), any en) in MMM(P))), we know En is an en- dogenous noise which may be confounded with tj. This means
E 15 Sh, ah, en. # O.
(3.3)
since е₁ also correlates with 4, Nevertheless, we note that ÉA independent of (sn, ax) in our model apart from what absorbed in R2, (sh, aj ex), the rest only depends the unobservable type ts which implies that
4. Meta Algorithm and Methodology
We're ready to present our algorithms to learn the optimal policy in the online strategic interaction model. We first introduce a mlta-algorithm (i.e., Algorithm 1), then come to its model- variant tailored for our setting.
Ey Fr Fh(-llnnandaal EA 8h, an) = 0,
5

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Algorithm 1 Meta Algorithm
IV
X
Y
1: Input: hypothesis class H. confidence level B, total episodes K, auxiliary function class U.
2: Initialize the exploration policy x² uniform policy.
3: for k ===1, -, K do
Sh an
Shz ah eh
The Sh+1
4: Establish dataset D with policy æ² for h E [H].
5: Compute empirical risk function (cs) ) for all en E
HA with auxiliary function class U.
6: Construct high probability confidence set Ch {c=
(c1,,.., CH) E H (((a) S B, vh E [
7: Compute c arg ce Vi, x Tek 1,
eh
f/
8: end for
9: Output: x² for i ~ Uni[([K]).
Figure 2. The causal graph for the strategic interaction between the principal and the h-th agent. The red line denotes the confounding between (ra, 81+1) and ty. "TV" means instrumental variables.
Suppose we have access to a hypothesis class H (Hr)A= h=1 that realizes the underlying model or equally value functions, we follow the optimism principle in the face of uncertainty to perform efficient exploration by se- lecting the optimistic hypothesis c++1 and its related policy Tot+1 (e.g., the optimal policy of cx+1 if ct+1 is the
Appendices and H for details on hyperparameter selection and additional information on another variant OPME-D.
model). The high probability confidence set is constructed by the empirical risk function with the help of an auxiliary function class 1/ (see Line in Algorithm 1) according to the casual identification established through our NPIV method (see Section 4.
It is challenging to estimate Rí, and P% from the model class because of the confounding issue. We take Rí, as an example explain this issue. Suppose the principal receives sampled reward rh at state 8n after taking action as and observing feedback En, one may hope E[(r [h,, an ex] = R%, (5), an, ex) so as to estimate R% by standard least square regression. However, this is not the case with the existence of confounders.
4.1. Detailed Explanation of Methodology
Recall that we face two coupled challenges aiming at leam- ing the optimal policy.
Given the endogenous noise En in rh. = R2 (on, any en. +E. Equation (3.3) implies that
First, we need to bypass the confounding issues. Since & which depends on unobserved type 4, appears in the reward function, the correlation between it and feedback en invalidates traditional direct reinforcement learning meth- ods, calling for instrumental variable method. As a simple observation, we know that the principal's state-action pair serves as a valid instrument. Intuitively, (s,, a²) affects the agent's 'ss reward both directly and indirectly only by affecting the feedback en generated from the agent's 's best response behavior.
(M- [r% sh, an, ane exl F (sh, an. en).
Here (P*) is the model under source distribution (cf. Section 3). Motivated by Yu et al. (2022); Angrist & Imbens (1995); Angrist & Krueger (2001); Chen & Qi (2022), we turn to tailoring the NPIV method and finally resolve this issue.
Nonparametric instrumental variable model. Since En is zero-mean noise, we can use (Sh, an) as an instrumental variable for (sh, ah, en) and rh. in the sense that (cf. Ap- pendix F)
Second, we need to explore unknown environments. Given the exploration requires accurate estimates of rewards and transitions, these two challenges are coupled and we propose a corresponding optimism principle generalizing the application of optimistic planning. We visualize the causal graph and our underlying intuition on instrumental variables in Figure 2.
Exc [rn - (7, an, en) sh, an) = 0.
(4.1)
Given any roll-in policy n. the conditional moment equation (i.e., Equation (4.1)) gives
We propose model-based variant of the meta-algorithm, i... OPME-G in Algorithm 2, in our setup, where the hy- pothesis class H4 is initialized to the model class H/, = (Rn, Pw), where Rr = {Ra+ R2 (sh, an, en) E R} and
E Sa
[Be, [rn R2 (5h ahs en.) 8h an]] = 0,
Pn = (Pp Ph(: 8h, an, ex) E A(S)). Please refer to
which inspires us to estimate R via the least-square loss in
6

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Algorithm 2 Optimistic Planning with Minimax Estimation- Dynamical/General (OPME-D/G)
empirical version of L say
1 k
1: Input: model class R. P. confidence level (see Equa- tion (H.4)), number of episodes K, discriminator class F, discriminator class G (used only in OPME-G).
(R(R))
del max fF.Fi.
(R fi)) -2 Rh ab). (R. f)
25
k
2: Initialize the dataset D,, = 0 for all h E [L.].
def Σ
(6 (R(s), oh e%,) r%)
(4.4)
3: Initialize the exploration policy x² as uniform policy.
4: for k k= 1, 2...... do
5: Roll out n5 and collect 7K = [(5 an chi +
Note that although the minimax estimation is motivated by Yu et al. (2022) which has access to i.i.d. samples for estimation, we can only process non-i.i.d but sequentially constructed dataset D.. It turns out that we need to resort to a different and more intricate fast martingale concentra- tion analysis with a new construction of confidence set (cf. Equations (4.7) and (4.8)).
6: for h = 2, .... H do
7: Add the sample (sh ab, c r s/+1) 1) to Ph.
8: Define the empirical risk function (-) of rewards RA E Rr by Equation (4.4).
Compute confidence set R2 by Equation (4.7). 10: Define the empirical risk function (-) of transi- tion dynamics G₁ E PA by Equation (D.4) for OPME-D, or Ps E Ph. by Equation (4.6) for OPME-G.
9:
The issue similarly affects the estimation of the transition function P7- Given 8/, d and eb. the confounding between the random variable 81+11 and ey impedes standard model- based estimation methods (Agarwal et al., 2020; Modi et al., 2021; Liu et al., 2022a). Nonetheless, the approach of value target regression (Ayoub et al., 2020; Zhou et al., 2021) inspires us and has been proven beneficial in addressing this confounding issue with meticulously tailored. We utilize additional discriminator class G. which is designed to encapsulate the optimal value functions of all candidate models. Specifically, for any Jh+11 within G and for any observed sn, an, it holds that
11:
Compute confidence set P by Equation (D.5) for OPME-D, or by Equation (4.8) for OPME-G. end for
12:
13:
Construct model class C+ by Equation (D.6) for OPME-D, or by Equation (4.9) for OPME-G.
14:
Set MM++1 = arg max Meca M (81) and xh+1 =
" "M+I-
end for
16:
Output: n² for i Uni]([A]).
EM-(PP)) (01+1(8844) Pigh+1 ahe en) 8h, 0h. 0,
episode k. that is.
(4.5)
thereby aiding in the effective resolution of confounding variables. This innovative approach allows for more accu- rate estimations of the transition dynamics by leveraging the capabilities of G to discriminate among the potential in- fluences of confounders. Note that the conditional moment equation has the same form as the previous one, namely, Equation (4.1). Therefore, we can similarly define the em- pirical risk function of PA as
arg min Rs.
Σ
[E [rA- Ru (sh, an; Cnte 8h, anl)²).
8y Ma
(4.2)
However, this conditional least-square regression cannot be directly estimated due to the conditional expectation inside the square. Instead, we use the minimax estimation with a discriminator function class Fs S x + R in place of Equation (4.2) by Rockaflla duality (Dai et al., 2018; Nachum & Dai, 2020) and we define the risk function L
(.(P)) del max P((hh.gh+)) 9h 1
(4.6)
(Ph. gh+1, fi) - 1 k Jn
(Phs gh+1) der
Σ fh a?,),
max
k
(1(((R))
def max (R Sh,, fn) IrEFa
s.and [[2(8, a)},
where ik de Σt s(3 a (P)((P))))) g(8
7=1
(4.3)
where (R. f) del Dtel
aad [f (R(sh
E.
Knowledge transfer and optimistic planning. We can estimate R² p* with consistent causal identification dis- cussed above. Leveraging the idea of unsupervised domain adaptation (Ganin et al., 2016), we then use such estimators to guide the exploration process given the target population by optimistic planning.
ah, (n) r-
In each episode k, we roll out a trajectory * (st, at, ctt of.... st ani ef. ( by & and construct a dataset DJ (7], ( ..... r².. Then we can construct an

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
To be more specific, construct the high probability confi- dence set in episode l: as
example, the second assumption requires discriminator func- tion class Fn. can capture the projection of i from the input space to the instrumental variable space in order to bound the error of corresponding minimax estimation.
R2 def
Rr E Rr (Ra)) S B1).
(4.7)
Ill- ul-posedness measure. We overcome the confounding is- sue through the NPIV model to build a consistent estimator of the model via conditional moment equations (i.c., Equa- tions (4.1) and (4.5)). Taking the reward functions as an example, these equations enable us bound the projected mean square error (MSE) of R,, namely.
P del Ph Ph (Ph) S 82)
(4.8)
The confidence level B1, S2 are defined in Equation (H.4). For all h and any Ry E R2 and Ps Ph. aggre- gated model M,, R, P) under the target distribution p with R= = {Ra { P- (Pn)) } is defined by Equations (3.1) and (3.2). which enables us to transfer the learned causal knowledge from the source population to the target popu- lation. Hence, we define the confidence set on aggregated models as
Bes Beeg [(RA R2)) (8h, ane en.) 8hh ]n]²]
while the sample complexity is associated with the MSE
E Rnn
(Ra(sn, On en) - R2 On, en))²]
en,))))
Ch dat (M(R, R. E Ri Pr E
PE vA E [A]]
(4.9)
Bridging the gap between projected MSE and MSE leads to an ill-posed inverse problem. People quantify the difficulty of this kind of problems via the following ill-posedness measure.
Finally, we choose the exploration policy k+1 for episode k 1 as the optimal policy of the model with the highest estimated cumulative reward in Chh Simply put, use Pe for estimation, use pt for exploration!
Definition 5.2. Define the ill-posedness measure Th as
E Esn.as.en wddt" [v] (sn, an. en)]
5. Theoretical Results and Analysis
del Th
max Ph
E Bnnaa Een (sh, ahe en) 8h, anl
In this section, we outline the assumptions made regarding the function classes and detail the sample complexity of our algorithms.
where the maximum of un. is taken over in E {RA R7 (Pr - p1)
5.1. Necessary Assumptions
The ill-posedness measure widely used in economics to quantify estimation errors of related instrumental variable models (Dikkala et al., 2020; Chen & Qi, 2022; Yu et al., 2022). It illustrates how confounders increase the difficulty of the learning problem and are inevitable in sample com- plexity.
Realizability. First of all, we require all the function classes be realizable.
Assumption 5.1 (Realizabilitt). There exists constant B such that for any h (H],
R2 E RR, PK E Ph.
Knowledge transfer error. Apparently, the knowledge transfer is infeasible when the target population drastically differs from the source population where the online data is collected (Pearl & Bareinboim, 2011). We quantify the error caused by transferring knowledge follows.
The auxiliary function class Fr S x A + R with range [-B, B] captures all required functions, say Pe.Pii,eFF(((e..e .)) [v (sn, an, an,e)] E Fr for any vh E (RA- Ry, (Pn- p.
Detinition 5.3. Detine the knowledge transfer multiplicative term Cj,
The auxiliary function class In : : + [-B, B] cap- tures all optimal value functions, say V MM.P)), E Gn of the aggregated model M(R, P) for any R e R. P.
Cf. def max Sp. an. d/.7 [uR ans et)] 14
E
E EP, Een.eheendd (sh an en]]
where 1n E (Ro, R2 (Pr -Pp))
Realizability is necessary since the identification is per- formed under general nonparametric function classes. For
The multiplicative term Cf, quantifies the distributional shift when transferring estimators computed from online data to the target population. In the literature, often referred
Recall that (P, Př Ga+1 = {Prge+1 Phight1 Py E Ph.gr+t E 9.+1).
8

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
to as "Concentrability" (Foster al., 2021b). Concentrabil- ity is simple but fairly strong notion of coverage, which requires that the distribution of our data collection evenly covers the target distribution we are interested in. It captures the effort needed to bypass the knowledge transfer.
6. Discussion and Conclusion
In this paper, we explore the theoretical impacts of infor- mation asymmetry and knowledge transferability within the context of reinforcement learning. Specifically, we concep- tualize these interactions using online strategic interac- tion model, framed through a generalized principal-agent problem, and we introduce algorithms designed to determine the principal's optimal policy within a MDP framework. We introduce innovative estimation techniques utilizing the NPIV method to address confounding issues stemming from information asymmetry. Additionally, we quantify the er- rors associated with knowledge transfer, providing a robust framework for understanding these dynamics in complex en- vironments. Finally, we propose an algorithm with ((1/²² sample complexity and show its optimality with respect to the optimality gap
5.2. Sample Complexity Results
We now introduce the sample complexity of our algorithms.
Theorem 5.4. Under Assumption 5. with probability at least 1 - 6, the sample complexity of the model-based algo- rithm to learn an e-optimal policy is bounded by
H1 Σ B'd CK log([R Px 6
Here d is the distributional Eluder dimension of the model class (cf. Appendix E).
Nevertheless, our model also has some limitations. For ex- ample, it requires the target distribution p' and the feedback manipulation distribution F to be known to the principal. There are two considerations on why we cannot remove this condition:
We use simple example to estimate the magnitude of the Fluder dimension and defer further discussion to Ap- pendix E.
Example 5.5 (Linear MDPs (Jin et al., 2021)). Consider the d-dimensional linear function classes
The optimal policy directly depends them but we assume no online interaction ability on the target popu- lation. That is to say, we need at least some (passive) samples on the target population to estimate the target distribution (e.g., by clustering). Also, it's a standard assumption in Myerson's 's auction and coordination the- ory of principal-agent problems (Myerson, 1981; 1982; Gan et al., 2022a) that the target type distribution is known.
R₂ = (0p TRd Rí (Sh: an. en) = T (sh, ar. en)
Ph =vh R² Pn(sn an en) o (sh, an: en),:n)) }
where @ is a known d-dimensional feature map- ping. We assume that the underlying reward func- tion is (s,,,, an: ex) = o (5h,, (h),))) en)0% for an unknown 8% while the true transition kernel is Ph (8h; an; en) = Φ (sh, on; 1 for some un- known v/g. Then, we know that dy S Ö(d), yielding ò OΣE Cd log(IR P x G FI/8) c22) sample complexity to learn a c-optimal policy.
The feedback manipulation distribution is often rela- tively easy to determine in reality. In many cases, it is either a canonical distribution known to the public or predetermined quantity according to the principal marketing research the target population.
Theorem 5.4 shows the sample complexity to learn optimal policy in such a general MDP setting scales as 0(1/²) with a linear dependency on the other terms, in- cluding dv,,. Th and C,,, The necessity of the ill ill-posed measure and knowledge transfer multiplicative term is dis- cussed in Appendix
Questions raise themselves for future explorations. We find that the states of such decision decision-making problems are not always fully observable (Brown & Sandholm, 2018; 2019; Futoma et al., 2020). For example, part of the attributes of third domain such as the government or market are unknown to both the principal and the agents. Is it possible to solve reinforcement learning problems with confounding issues under partially observable Markov decision processes (POMDPs)? Is the NPIV method still valid with value bridge functions (Shi al., 2021; Uehara et al., 2022a;b)) We leave these interesting questions as potential next steps.
Lastly, we end this section with remark relevant lower bounds.
Remark 5.6. Domingues al. (2021) proves that an Ō log(1/6)) sample complexity is inevitable to identify an c-optimal policy with probability 1 8 even without con- founding issues. Hence, we conclude that our algorithms achieve optimal, though omitting logarithmic terms, sample complexity concerning c. The dependence of lower bounds on problem- deleedde-eeeeeettt parameters is of independent interest, and we leave it as a future research avenue.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
consequences of our work, none which feel must be specifically highlighted here.
Ben-David, S. and Urner, R. Domain adaptation-can quan- tity compensate for quality? Annals of Mathematics and Artificial Intelligence, 70: 185-202, 2014.
References
Bennett, A. and Kallus, N. Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. arXiv preprint 1rXi::2110.153222 2021.
Abhasi-Yadkont Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algo- rithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Bennett, A., Kallus, N., Li, L., and Mousavi, A. Off Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders. In International Conference on Artifi- cial Intelligence and Statistics, pp. 1999-2009 PMLR, 2021.
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. Flambe: Structural complexity and representation learn- ing of low rank mdps. Advances in neural information processing systems, 33:20095-20100 2020.
Bernasconi, M., Castiglioni, M., Marchesi, A., Gatti, N., and Trovò, F. Sequential information design: Learning to persuade in the dark. arXiv preprint MxXi::209.03927. 2022.
Ai, C. and Chen, X. Efficient estimation of models with con- ditional moment restrictions containing unknown func- tions. Econometrica, 71 (6):17955-188)) 2003.
Blundell, R., Chen, X., and Kristensen, D. Semi- nonparametric iv estimation of shape-invariant engel curves. Econometrica, 75(6):1613-166) 2007.
Angrist, D. and Imbens, W. Two-stage least squares es- timation of average causal effects in models with variable treatment intensity. Journal of the American statistical Association, 90(430):431-443 1995.
Brero, G., Eden, A., Chakrabarti, D., Gerstgrasser, M., Li, V., and Parkes, D. C. Learning stackelberg equilibria and applications to economic design games. arXiv preprint arXiv:2210.03852,, 2022.
Angrist, J. D. and Krueger, A. B. Instrumental variables and the search for identification: From supply and demand to natural experiments. Journal of Economic perspectives, 15(4):69-88) 050:6699552220 2001.
Brown, N. and Sandholm, T. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
Auer, P., Jaksch, T., and Ortner, R. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Brown, N. and Sandholm, T. Superhuman ai for multiplayer poker. Science, 365(6456):885-89)) 2019.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang. L. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Cai, Q. Yang, Z., Jin, C., and Wang. Z. Provably efficient exploration policy optimization. In International Con- ference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Azar, M. G., Osband, and Munos, R. Minimax regret bounds for reinforcement learning. In International Con- ference on Machine Learning. pp. 263 272. PMLR, 2017.
Chen, S. and Zhang, B. Estimating and improving dynamic treatment regimes with time-varying instrumental vari- able. arXiv preprint arXiv: (ttt:2104.0782... 2021.
Bareinboim, E. and Pearl, J. Causal transportability with limited experiments. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 27, pp. 95-101, 2013.
Chen, X. and Pouzo, D. Estimation of nonparametric condi- tional moment models with possibly nonsmooth general- ized residuals. Econometrica, 80(1):277-321, 2012.
Başar, T. and Olsder, G. J. Dynamic noncooperative game theory. SIAM, 1998.
Chen, X. and Qi. Z. On well-posedness and minimax op- timal rates of nonparametric q- q-function estimation in off-policy evaluation. arXiv preprint trXiv:2201.06/66 2022.
Ben-David, S. and Urner, R. On the hardness of domain adaptation and the utility of unlabeled target samples. In Algorithmic Learning Theory: 23rd International Con- ference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pp. 153. Springer, 2012.
Chen, X. and Reiss, M. On rate optimality for ill ill-posed inverse problems in econometrics. Econometric Theory, 27(3):97--52,, 2011.
10

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Chen, X., Hu, J., Yang, L. F., and Wang. L. Near-optimal reward-free exploration for linear mixture mdps with plug-in solver. arXiv preprint arXin:2110.03244, 2021.
Futoma, J., Hughes, M. C., and Doshi-Velez, F. Popcorn: Partially observed prediction constrained reinforcement learning, arXiv preprint arXiv:2001.04032 2020.
Chen, Z., Li, J., Yuan, A., Gu, Q., and Jordan, M. I. A general framework for sample-efficient function ap- proximation in reinforcement learning. arXiv preprinl arXiv:2209.15632 2022.
Gamrian, S. and Goldberg, Y. Transfer learning for related reinforcement learning tasks via image-to- toiiaagg transla- tion. In International conference on machine learning. pp. 2063-2072. PMLR, 2019.
Conlisk, J. Why bounded rationality? Journal of economic literature, 34(2):669-700, 1996.
Gan, J., Han, M., Wu, J., and Xu, H. Optimal coordination in generalized lancipal-agenn problems: A revisit and extensions. arXiv preprint arXiv:2209.01 002200000144 146, 2022a.
Dai, B., Shaw, A., Li, L.., Xiao, L.,, He, N., Liu, Z., Chen, J., and Song, L. Sbeed: Convergent reinforcement learn- ing with nonlinear function approximation. In Interna- tional Conference on Machine Learning, pp. 1125-1134. PMLR, 2018.
Gan, J., Majumdar, R., Radanovic, G., and Singla, A. Bayesian persuasion in sequential decision-making In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 5025-5033 2022b.
Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., Marchand, M., and Lempitsky, Domain-adversarial training of neural networks. The journal of machine learning research, 17(1):2096 2016.
Dann, C., Li, L., Wei, W., and Brunskill, E. Policy cer- tificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pp- 1507-1516. PMLR, 2019.
Guruganesh, G., Schneider, J., and Wang. J. R. Contracts under moral hazard and adverse selection. In Proceed- ings of the 22nd ACM Conference on Economics and Computation, pp. 563-582, 2021.
Devroye, I.., Mehrabian, A., and Reddad, T. The total variation distance between high-dimensional gaussians. arXiv preprini arXiv: 1110.0861110.09 2018.
Hall, P. and Horowitz, J. L. Nonparametric methods for inference in the presence of instrumental variables. 2005.
Dikkala, N., Lewis, G., Mackey, L., and Syrgkanis, V. Mini- max estimation of conditional moment models. Advances in Neural Information Processing Systems, 33:12248 12262, 2020.
Hamilton, J. D. and Whiteman, C. H. The observable impli- cations of self-fulfilling expectations. Journal of Mone- tary Economics, 16(3):353-373) 1985.
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598. PMLR, 2021.
Harris, K., Ngo D. D. T., Stapleton, L., Heidari, H., and Wu, S. Strategic instrumental variable regression: Recovering causal relationships from strategic responses. Interna- tional Conference on Machine Learning, pp. 8502-8522. PMLR, 2022.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Hu, J., Chen, X., Jin, C., Li, L., and Wang, L. Near-optimal representation learning for linear bandits and linear rl. In International Conference on Machine Learning, pp. 4349 PMLR, 2021.
Dubey, A. and Pentland, A. Provably efficient cooperative multi-agent reinforcement learning with function approx- imation. arXiv preprint wxxiv:2103.0997 2021.
Hua, J., Zeng. L., Li. G., and Ju. Z. Learning for robot: Deep reinforcement learning, imitation learning, transfer learning, Sensors, (2)) 2021.
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing. arXiv preprint arXiv:21 12. 13487, 2021a.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable In International Con- ference on Machine Learning. pp. 1704-1713, PMLR, 2017.
Foster, D. J., Krishnamurthy, A., Simchi-Levi, D., and Xu, Y. Offline reinforcement learning: Fundamental barri- ers for value function approximation. arXiv preprint (0.:://11.199) 2021b.

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? Advances in neural infor- mation processing systems, 31, 2018.
Maskin, E. and Riley, Monopoly with incomplete informa- tion. The RAND Journal of Economics, 15(2):171-196, 1984.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforcement learning with linear function ap- proximation. Conference on Learning Theory, pp- 2137-2143, PMLR, 2020.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, N., and Agarwal, A. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07033. 2021.
Myerson, R. B. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981.
Jin, C., Liu, Q., and Miryoosefi. S. Bellman eluder di- mension: New rich classes of rl problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:13406-1333 13418, 2021.
Myerson, R. B. Optimal coordination mechanisms in gener- alized principal-agen problems. Journal of mathematical economics, 10(1):67-81, 1982.
Kallus, N. and Zhou, A. Confounding-robut policy evalua- tion in infinite-horizon reinforcement learning. Advances in Neural Information Processing Systems, 33:22293- 22304, 2020.
Nachum, O. and Dai, B. Reinforcement learning via fenchel- rockafellar duality. arXiv preprint arXiv:2001 006666 2020.
Kallus, N. and Zhou, A. Minimax-optimal policy learning under unobserved confounding. Management Science, 67 (5):2870-2890, 2021.
Nair, Y. and Jiang, N. A spectral approach to off-policy evaluation for pomdps. arXiv preprint arXiv:2109. 2021.
Newey, W. K. and Powell, J. L. Instrumental variable esti- mation nonparametric models. Econometrica, 71(5): 1565-1578, 2003.
Kamenica, E. and Gentzkow, M. Bayesian persuasion. American Economic Review, 10166):550-2615, 2011.
Kumar, H., Musabirov, I., Reza, M., Shi, J., Kuzminykh, A., Williams, J., and Liut, M. Impact of guidance and interaction strategies for IIm use on learner performance and perception. arXiv preprint 2rXiv:2310.1377
Pan, S. J. and Yang, Q. A survey on transfer learning. IEEE Transactions on knowledge and data engineering, 22((0): 1345-1359, 2009.
2023. Liao, L., Fu, Z., Yang, Z., Wang. Y., Kolar, M., and Wang, Z. Instrumental variable value iteration for causal offline reinforcement learning. arXiv preprint arXiv:2102.09900 2021.
Pearl, J. Causality. Cambridge university press, 2009.
Pearl, J. and Bareinboim, E. Transportability of causal and statistical relations: formal approach. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 25, pp. 247-254, 2011.
Littman, M. L. Markov games as a framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
Russo, and Van Roy, Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013,
Liu, Q., Chung, A., Szepesvári, C., and Jin, C. When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.08967 2022a.
Sabater, and Sierra, C. Review on computational trust and reputation models, Artificial intelligence review, 24: 33-60, 2005.
Liu, Q. Netrapalli, P., Szepesvari, C., and Jin, C. Opti- mistic mle-a a generic model- based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209.14990 2022b.
Shi, C., Uehara, M., and Jiang, N. A minimax leam- ing approach to off-policy evaluation in partially ob- servable markov decision processes. arXiv preprint arXiv:2111.0677 2021.
Lu, M., Min, Y., Wang, Z., and Yang. Z. Pessimism in the face of confounders: Provably efficient offline reinforce- ment learning in partially observable markov decision processes. arXiv preprint arXiv:2205.133: 2022.
Simon, H. A. Bounded rationality. Utility and probability, pp. 15-18, 1990.
Sun, W., Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. Model-based rl in contextual decision pro- cesses: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2898 2933. PMLR, 2019.
Mandal, D., Triantafyllou, S., and Radanovic, G. Per- formative reinforcement learning. arXiv preprint arXiv:2207.00046, 2022.
12

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Yang. T., Wang, W., Tang, H., Hao, J., Meng, Z., Mao, H., Li, D., Liu, W., Chen, Y., Hu, Y., et al. An efficient transfer learning framework for multiagent reinforcement learning. Advances in neural information processing systems, 34: 17037-17444 2021.
Taylor, M. E. and Stone, P. Transfer learning for reinforce- ment learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.
Yu, M., Yang. Z.,, and Fan, J. Strategic decision-making in the presence of information asymmetry: Provably ef- ficient rl with algorithmic instruments. arXiv preprint arXiv:2208. / 1040, 2022.
Tennenholtz, G., Shalit, U., and Mannor, S. Off-policy eval- uation in partially observable environments. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Interna- tional Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Uehara, M., Kiyohara, H., Bennett, A., Chernozhukov, V., Jiang, N., Kallus, N.. Shi, C., and Sun, W. Future- dependent value- based off- off-policy evaluation in pomdps. arXiv preprint arXiv:2207. 13081, 2022a.
Uehara, M., Sekhari, A., Lee, J. D., Kallus, N., and Sun, W. Provably efficient reinforcement learning in par- tially observable dynamical systems. arXiv preprint arXiv: 12020, 2022b.
Zhang, H. and Conitzer, V. Automated dynamic mecha- nism design. Advances in Neural Information Processing Systems, 34:27785-27797, 2021.
Zhang, Z., Ji, X., and Du S. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference Learning Theory, pp. 3858- 3904. PMLR, 2022.
Wang. J.. Qi. Z., and Shi, C. Blessing from experts: Su- per reinforcement learning in confounded environments. (tt.:2209./5445 2022.
arXiv preprint
Wang, L., Yang, Z., and Wang, Z. Provably efficient causal reinforcement learning with confounded observational data. Advances Neural Information Processing Sys- tems, 34:21164 2021.
Zhong, H. Yang. Z., Wang. Z., and Jordan, M. I. Can reinforcement learning find stackelberg nash equilibria in general-sum markov games with myopic followers? arXiv preprint arXiv:2112.13522 2021.
Wang, R., Salakhutdinov, R. R., and Yang, L. Reinforce- ment learning with general value function approximation: Provably efficient approach via bounded eluder dimen- sion. Advances in Neural Information Processing Sys- tems, 33:6123-6135, 2020.
Zhong, H., Xiong, W., Zheng, S., Wang. L., Wang. Z., Yang, Z., and Zhang, T. A posterior sampling frame- work for interactive decision making. arXiv preprint arXhv:2211.0166,, 2022.
Wang, Y., Hu, J., Chen, X., and Wang, L. Distributed bandit learning: Near-optimal regret with efficient communica- tion. arXiv preprint arXiv: 1904.06309, 2019.
Zhou, D., Gu, Q. and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532-45555555 4576. PMLR, 2021.
Wu, J., Zhang, Z., Feng, Z., Wang, Z., Yang, Z., Jordan, M. I., and Xu, H. Sequential information design: Markov persuasion process and its efficient reinforcement learn- ing. arXiv preprint arXiv: 10678, 2022.
Zhu, Z., Lin, K., Jain, A. K.,, and Zhou, Transfer learning in deep reinforcement learning: A survey. IEEE Trans- actions Pattern Analysis and Machine Intelligence, 2023.
Yan, Z., Jouandeau, N., and Cherif, A. A. A survey and anal- ysis of multi-roboo coordination. International Journal of Advanced Robotic Systems, 10(12):399, 2013.
Zhuang. F., Qi, Z., Duan, K., Xi. D., Zhu, Y., Zhu, H., Xiong, H., and He, Q. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1):43776, 2020.
Yang, L. and Wang, M. Sample-optimal parametric q- learning using linearly additive features. In Interna- tional Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Yang, L. and Wang. M. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In In- ternational Conference on Machine Learning, pp. 10746- 10756. PMLR, 2020.
13

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
A. Notation Table
For the convenience of the reader, we summarize the notations in the paper as a notation table.
Notation
Explanation
S,A, P. R1
parameters of an online strategic interaction model state, action, feedback, private type step h the space of MMstte history (Z₁, excludes the state sn an M-step history in 2n. 2%
8h, ahe Chi ln
Zh. Zh.
2/: 3h.
P8 PPi, P::.., 2.... Pi))
the distribution of private types on source population
Pt P?... PHH)
the distribution of private types on target population private reward function of the agent with type and action b private action of the h-th agent feedback manipulation distribution
12, sh Oh, t,
by arg max, (sh, ah th.
( sh. on; ln, bn)
F.l. Sh. an. th)
F- (- Sh,, d₁2 th arg max, R2 ($h. ah tn, b)), equivalent to Fh.
MP
the online strategic interaction model under the source/target population occupancy measure of sh, ahs, En on M (P'),,
d (sh, ahs Eh), dh (sh, an, en)
T (Sh, an), d, an)
occupancy measure of sh, an on (P*) M'()) confidence level
8, 12,1,,2,99 93
R (R1, RH), P (P1,.., PH)
hypothesis model class
RG (sh; ah, eh), ) PR (5h (h,Ch eh)
underlying reward function and transition function aggregated reward and transition target population aggregated MDP model on target population
PR, R
M = A, P", RR,R"" H1)
#*
optimal Markovian policy of MM value function of policy π on M² additive endogenous noise rewards discriminator function class
En
F (FI,,,.., (9,,
Pigh+1 a/s, ex)
Bellman backup E. 1h+1 sh, an en.) population risk function of candidate models empirical risk function of candidate models confidence set
1
I 1
Rt, Ph, Ch Chk Th
ill-posed measure knowledge transfer multiplicative term distributional Eluder dimension of the model class any function in the union space of RR - Ri and (P^ - Gr))
Ci
dv,,, dv.k
ph (main text)
G (Gi, G²
dynamical system transition function (cf. Appendix D.1)
d,
the dimension of the state in dynamical system
Ph.s, GGn, Phis)
dynamical transition class and one function in the class for dim i [d.]
Vn
the union space of Rr Rí (Ph. P7) Ph,i Gh, Vi E [da] any function in V%:
ph (appendix)
B. Detailed Discussion of Related Work
We discuss some related works in detail in this section.
B. Further Topics and Related Work
In this section, we provide a more in-depth and comprehensive discussion of the related literature.
Online exploration in MDPs. Online exploration problem is of the most fundamental problems in reinforcement
learning (Sutton & Barto, 2018). It has been extensively studied in tabular MDPs (Auer et al., 2008; Azar et al., 2017; Dann et al., 2017; Jin et al., 2018; Dann et al., 2019; Zanette & Brunskill, 2019: Zhang et al., 2022), MDPs with linear function approximation (Yang & Wang, 2019; Jin et al., 2020; Yang & Wang. 2020; Cai et al., 2020; Ayoub et al., 2020; Agarwal et al., 2020: Zhou et al., 2021: Hu et al., 2021; Chen et al., 2021) and general function approximation (Russo & Van Roy, 2013; Jiang et al., 2017; Sun al., 2019; Wang et al., 2020; Jin et al., 2021; Du et al., 2021; Foster et al.,
14

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
202 Zhong et al., 2022; Liu et al., 2022b; Chen et al., 2022). In the standard exploration problem, the agent is required to balance the exploration-actively exploring the unknown part of the environment to discover potential high rewards, and the exploitation-exploiing the discovered area to earn higher rewards. The exploration-exploittion trade-off is known as one of the core challenges in RL with large state and action space. This paper studies the online strategic interactions in RL with general function approximation, which naturally inherits the exploration-exploiatiio trade-off challenge. Furthermore, the strategic interaction model presents a more challenging exploration issue in that the agent is able to manipulate the distribution of the strategic feedback based on her private type, which not controlled by the principal. We tackle this issue by leveraging the NPIV model (Ai & Chen, 2003; Newey & Powell, 2003) and optimism in the face of uncertainty principle (Abbasi-Yadkori et al., 2011).
RL with confounders. Our work is also related to RL with confounders, as the private type f, acts as an unobserved confounder in the strategic interaction model. The off-policy evaluation (OPE) problem with unmeasured confounders has been actively studied in recent years (Kallus & Zhou, 2020; Temnenholtz et al., 2020; Shi et al., 2021: Bennett & Kallus, 2021; Bennett et al., 2021; Nair & Jiang, 2021) by leveraging the techniques in casual inference (Pearl, 2009). There are also a number of works studying the policy optimization in offline RL with a confounded dataset (Wang et al., 2021; Liao et al., 2021; Kallus& & Zhou, 2021; Lu et al., 2022; Yu et al., 2022; Wang et al., 2022). On the contrary, our work studies the online setting, where the unobserved private type tn confounds with the rewards and transition dynamics. Among these works, the most related one to us is Yu et al. (2022), which studied the strategic MDPs in the offline setting. Our work is different from theirs in several aspects. First, we study the strategic interactions in the online setting which violates the widely used i..d. assumption and calls for new technical solutions. Second, we explore setup that more accurately transportability. Lastly, we extend their transition class
simulates the real world, albeit with an added baallenge-knowlee from nonlinear dynamical systems to general transition classes, which can handle noises that are not additive. We refer the readers to Appendix B.2 for a detailed comparison.
Transfer learning for reinforcement learning domains. Taylor & Stone (2009) gives an inspiring survey on how to do transfer learning when facing RL scenarios while Zhu et al. (2023) extends it to deep reinforcement learning. As for the application literature, Hua et al. (2021) utilizes transfer learning and reinforcement learning in the field of robotics and Gamrian & Goldberg (2019) uses this idea to solve visual tasks. Yang et al. (2021) considers how to use transfer learning when facing multiagent reinforcement learning. Here, we give some theoretical perspectives on how knowledge transportability affects the sample complexity of reinforcement learning.
B.2. Novel Analysis Beyond the Offline Strategic MDP and Standard Exploration in RL
We discuss the novelties of our algorithms beyond the PLAN algorithm proposed by Yu et al. (2022) that learns the optimal policy of strategic MDPs under general function approximation in the offline setting, and the exploration algorithms in standard RL literature with general function approximation. The novelties mainly come from the problem settings and theoretical analysis, besides the difference between online exploration and offline planning.
In terms of the problem settings, we study generalized version of the original strategic MDPs proposed in Yu et al. (2022), which assumed the transition dynamics belong to a nonlinear dynamical system class with additive Gaussian noises. We show how to learn the optimal policy in general transition classes (cf. Section 4.1) given access to an extra discriminator function class. Moreover, we study a generalized online strategic interaction model that breaks static policy assumptions and needs to balance exploration and nuisance caused by time-varying data, Our analysis, focusing the utilization of correlated data as instrumental variables, is entirely independent from their work, which introduces novel design and analysis for a new NPIV model.
In terms of the theoretical analysis, ours are different from the analysis in Yu et al. (2022) in three aspects: the casual identification, the construction of the confidence set, and the analysis therein.
Although both our work and their work take advantage of the NPIV model to estimate the empirical risk function i (see, e.g., Equation (4.4)), Yu et al. (2022) established the concentration bound with an i.i.d. distributed dataset, but our work employs martingale concentration analysis with Freedman's 's inequality. Moreover, their work constructed the confidence set by restricting the value difference between a candidate model and the minimizer of i, while we construct the confidence set by solely restricting the value of i of the candidate model (see, e.g., Equation (4.7)). Our analysis shows that our construction not only cleaner but enables us to get rid of the symmetric and shar-shaped
15

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
assumption imposed on F (see Assumption 5.3 of Yu al. (2022)). Moreover, we design cleaner proofs only using the realizabilityy assumption and the boundedness of zeros of concave quadratic function, simplifying the complicated proof based on the symmetric and star-shaped assumption of JF in Yu et al. (2022).
In an online strategic interaction model, the principal is asked to interact with a source population of agents for H steps, where each agent has a private type and commits a private action, both unknown to the principal. The goal of the principal is to learn a return-mant maxumiiin policy for another population of agents called the target population. The property of the source population is described through the private type distribution of the agents Pe (the source distribution), and the feedback manipulation distribution F. The source distribution is unknown to the principal. For the feedback manipulation distribution F, we made a simplification in the paper to assume it is the same for the source population and target population, but we note that this distribution can be different for the source and the target. The principal does not need to know the corresponding F of the source population. This is part of the reason why we cannot reduce the problem to a naive single-agent RI. problem since the source distribution and source feedback manipulation distribution are both unknown. Another challenge beyond single-agent RL is the distributional shift between the source distribution and the target distribution. Our model-based approach follows a similar idea of unsupervised domain adaptation where we estimate the underlying model Rt, P from the source distribution at first, then transfer the estimator to the target. A key difference the unsupervised domain adaptation here is the use of target distribution. Standard unsupervised domain adaptation uses target distribution to build importance-samplinn estimators. Nevertheless, as we don't 't know Pt, it's impossible to use importance sampling to construct an unbiased or even consistent estimator. Besides, confounding issues beyond traditional RL problems hamper our use of importance sampling as well. Consequently, we use the target distribution to design the exploration policy for the next episode.
C. Detailed Descriptions of the Online Strategic Interaction Model and the Motivation
This section offers more details of the online strategic interaction model and the motivations to learn this model.
C.1. More Details of the Online Strategic Interaction Model
For a strategic interaction model M (P) with reward function R", transition dynamics P", and agent private type distribution P. the casual graph of the strategic interactions between the principal and the h-th agent is shown in Figure 2. To better illustrate this strategic interaction process, we take the reward ry as an example. The causal structure of the transition 8h+1 is the same as rh-
The reward equals
Th R5 Obe e1) + En
by definition, where En. is an endogenous noise that may be confounded with ta (Yu et al., 2022; Harris et al., 2022).
Definition C.1 (Informal, see Pearl (2009) for a formal definition). A factor in a causal model or causal system whose value determined by the states of other variables in the system is called an endogenous variable. On the contrary, an exogenous variable is factor in a causal model or causal system whose value is independent of the states of other variables in the system.
According to the definition and observe that &n is only confounded with the private type th, it holds that
ERa (EA 8h, ax) = 0.
(C.1)
Now, let's talk about why Equation (C.1) makes sense. Considering the source distribution Ps, if EP, [EA shs anl * 0, we can set R2, (Sh. an. ex) to be R2 (Sh, an; en) + ER,, [Ex. 8h, az). Then, this process demeans En and proves the legitimacy of Equation (C.1), namely, we can assume En is zero-mean under Pd without loss of generality. Nevertheless, we in general cannot guarantee that Eps, [sx I sh. an] = O whenever the target distribution pt is deviated from the source distribution P Note that En. doesn't 't depend on ag actually, so the optimal policy under dynamics R7 (s), on en) and R2 (sh; 0n, ex) + EP
Pt, (Et] 8h, an] are the same. Consequently, albeit adding the counterfactual assumption that
Ex,, [5x sb. anl = O, we will find an identical policy as the case without it regarding the way we form M'. Therefore, we conclude that assuming Hp [5h 8h, on] = O won't 't simplify the problem and will yield equivalent sample complexity.
16

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Thereupon, keep Equation (C.1) for a more concise presentation and want remind readers that this assumption is neither necessary nor does it affect the results.
However, this confounding issue causes a severe challenge that when conditional on any (sh. Op. Ca)
(P) [FA 8%: ab. enl * R2 (8h, ahs en)
because the feedback eμ also depends with La and the noise term En will not be zero-mean given c Observe that conditioned on any (5h, aA) it holds that (P)) [r% 8h; anl
Bag ~ Pa [rk Sh, sh,anl anl
Brg Pr Paltlan [R* (8h, On, ex)l
(C.2)
The second equation holds because of Equation (C.1). The last term in Equation (C.2) is the definition of the aggregate model (i.e., Equations (3.1) and (3.2)).
The transition dynamics have the same causal structure of the rewards, but we cannot express this structure with additive endogenous noise as the rewards. The causal identification of the next state 8h+1 should be
Sh+1 Pe (lom,, [P (sh, an, en]]
according to previous analysis. Therefore, the expected reward and transition are identical for the corresponding strategic interaction model M (P) and the aggregated model.
C.2. Motivating Examples
We offer two motivating examples here for the MDP setting.
The non-compliant agents in the recommendation system (Yu et al., 2022). The principal is a company offering some recommendation services, and the agents are clients. The private types t, are the profiles of the clients (e.g., the category of items they like, and their shopping preferences). The state 8p is a public condition of the company (e.g., the inventory level, the transportation service condition, etc.), and the action ag the recommended item to the client. The private action b; is the item ordered by the client (not necessarily the same as an), and the feedback en exactly the action by, in this case. The reward тı is the real profit made from this client, which is related to the state Sh, the feedback e사 b,. the transportation fee, the willingness to buy accessories, etc. In this case, the reward distribution is highly correlated to the private type th, and such correlation can not be expressed by a simple model R(s), ans en) with an independent additive noise. That explains the necessity to introduce a confounding noise model and thus endogenous variables. Here, H = 12 represents 12 months in one year periodically.
The admission of university (Harris et al., 2022). A university (the principal) is making admission decisions for a population of applicants (the agents). Typically, there are several, namely H, rolling admissions decisions throughout the year. The action an of the university is an assessment rule that measures some predicted outcome (such as the overall GPA) of the students if admitted. The predicted outcome is also used as the reward thh for the university. The feedback е₁ should be some observed/measured attributes of the students, like the standardized test scores, high school GPA, etc. The students try to maximize the alignment between the observed attributes e), and the assessment rule Gg through their efforts by. which is unobservable. The private type I of the student can be many (unobserved) attributes related to é₁ or Tı (the predicted outcome of the student), such as the baseline scores the students can get without any efforts, the efficiency of changing efforts to improved scores, etc. The noise term & summarizes all other environmental factors that can impact the agent's true outcome when we control for observable attributes, such as the effect of the institutional barriers the student faces on their actual college GPA. The noise term &n can be arbitrarily correlated with private type t, which also impacts the feedback e/.
D. Complete Algorithm in the Online Strategic Model
The complete algorithm, Optimistic Planning with Minimax Estimation (OPME), is presented as Algorithm 2. We provide OPME for two types of transition classes: the general transition class (cf. Section 4.1) and the dynamical transition class (see Appendix D. The algorithm OPME-Geners (OPME-G) is the complete version of the model-basee based algorithm described in Section 4.1.
17

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
D.I. The Dynamical Transition Class
Following the setting of Yu et al. (2022), we also study restricted transition class that Ph a non-linear dynamical system. Suppose S Rd and
1 G7 (St, Cb, Ch) V/
for some unknown G where 7h is a dd-dimensional zero-mean noise possibly confounded with ty. Thus, we assume the noise term 77 can be decomposed to correlation term and an independent noise
M/ corr(I:) + T/e
(D.I)
where corr(-) is correlation function and v// is an independent standard Gaussian noise 1/h, (O0 Id,). In such transition classes, Pa be written Pn { G1,, (Gh,1,, Gh.,, ... Gi.d,) } For simplicity, assume Ph can be decomposed as the product of dg classes Ph, Ph.1 Ph.2 x ... x Ph,d, where
PA.s {Gr,a: Gs,,(Sk, Ch, eh) R}
(D.2)
denotes the transition class for the i-th coordinate and step h. Note that Gia Ph, for each i [dy].
We propose the algorithm OPME-Dynamical (OPME-D, Algorithm 2) that learns the optimal policy of MM*(P!) under the dynamical system transition class.
Similar to the reward function, the identification of the transition function can also be established by the NPIV method, that is
EM-((=)) [sh+1 Gi, 0h: an; en) 8h, an) = 0.
(D.3)
For E [d.]. we can construct the empirical risk function [. for transition GA,i analogously. With a little abuse of notations, we define
(Gr,)) del max FREF
(G fh)
1 Σ ah)
(D.4)
2
and
ih (Gn,i, fi)
(1) (Ghalsho The ( sh+,))
The high probability confidence set in episode for the transition function is defined as
Pk: del {Gnn Pha (K(Gn.)) S 83) vi [d]].
(D.5)
Here 33 (defined in Equation (H.4) is the confidence level used in OPME-D. For all and any Rg E R and G₁, E Ph def
Th Pk. h.i
4 we can construct the aggregated model M(R, G) under the target distribution p with R = (R, 11 (= by Equations (3.1) and (3.2). Hence, we define the confidence
[h G
aggregated models
ckk ش del (M(R,G) G): Rd E R GR. P vh [H]]-
(D.6)
We choose the exploration policy for episode & + 1 as the optimistic policy with the highest value in C*
E. The Distributional Eluder Dimension
Definition E.1 (e-iddependence between distributions, Definition 6 of Jin et al. (2021)). Let G be function class defined on X, and (1,42, .... Mn be probability distributions over X'. We call is c-independent of pr, H2.... Pa with respect to G if there exists g E G such that / VE (Ep, (z) < c, but [g] > e.
*We use - ph as the shorthand for Pk, x Ph X Pk Ph.d
18

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Definition E.2 (Distribational Eluder Dimension, Definition 7 of Jin et al. (2021)). Let & be function class defined on X, and IT be class of distributions over X. The distributional Eluder dimension dimpE (9, II, e) is defined the length of the longest sequence Mi, M2, Mn. such that μi E 1I, Vi E [n] and there exists e' 2 where μ4 is e' -'indeppenden of Mi.... Mi-1 for all i E [n].
We define the distribution class II = {II h= where II,, collects all the density measures dx," for the optimal policy x of any aggregated model MRR P). R E R, P.P.
For dynamical system transition class, with a little abuse of notations, we define the distributional Eluder dimension dm of the model class (R, P) by
d
dy def dimpe Rí 1I, 1/VK)/ + dimpe (Pnp Ph II 1/vK).
For the general transition class, we define the distributional Eluder dimension dy of the model class (R, P) with respect to the discriminator function class G as
dv. dimpa (R₁, Rip, II,, 1/vK) dim PA I,, 1/VK).
The distributional Eluder dimensions are small for several model classes (Jin al., 2021; Jiang et al., 2017). Here we provide detailed example.
Consider the d-dimensional linear function class
RA = {0r, E Rdd (s ah, en.) = (T (sh, Ore en )n,
where & is known d-dimensional feature mapping. The underlying reward function is R2 (8h, 0n, en) = x5 (sh, 0h, 00, for an unknown 0% Then for any RA E Rr, there exists a feature function 4// II + Rd such that
enn"d"" [Ra an. ex) - R2, (sh. an en) = (1h (T), -0,--
(E.1)
where
(x(T) = E ea [o(sh, On ex)]-
According Section C.I of Jin et al. (2021) and Equation (E.1), we know
dimpe(R, - R II, 1/ 1/VK)
as long as || ||0x ll2 have a uniform upper bound.
Similarly, bound the distributional Eluder dimension of Ph.i if
Ph.; (6h E Rd: (h,i(Sh, an, en) = & (8h, ah, en )6,
The distributional Eluder dimension is bounded by
dimpe - Ph. 1I, 1/VK)/ S (d)))
for each E [d+]. More generally, consider general transition class with a linear structure
PA {-n(-) E Rd Ph(. (:1 sh, Gh, en) = o [sh ar, en (x)))
where yn (.) is measure over S. Then
PhGh+1 = ((o.mn())) e Gh+1 x d: Phght1 (Sho ah, en) = (loh) ans fmulol((sdds)
19

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
which is again linear function class with respect Φb. Therefore, still have
dimpE (Pr9h+1 - 11, HI, 1/vK)s0(d)
if || and Il J, (s)ddsl both uniformly upper bounded.
As final remark, there are also other function classes whose distributional Eluder dimension is small, such the generalized linear function class (Russo & Van Roy, 2013; Jin et al., 2021), the kernel function class with bounded effective dimension (Jin et al., 2021; Du et al., 2021). Since this is not the main point of the paper, we refer the readers to the mentioned papers for further details.
F. The Nonparametric Instrumental Variable Model
We have provided detailed explanation of the causal structure in the strategic MDP in Appendix C. In this section, show that we can use the nonparametric instrumental variable (NPIV) model (see, e.g.. Dikkala et al. (2020); Chen & Qi (2022)) to estimate the underlying model Rº and P
Recall the general form of the NPIV model (Chen & Qi, 2022)
Y fx)) U. with EIU W| = 0,
where f is the unknown function to estimate, is the response, X called endogenous variables, W called instrumental variables, and U is the random (endogenous) noise.
According the causal relationship (see Figure 2), the NPIV model is exactly applicable to estimate P and R with Y (Th; 8141), (T X (5h, ah, ex), and W (sh, an) since the noise U is zero-mean in the population level (see, e.g.. Equation (C.1)).
To solve for f", we build the conditional moment equation (Dikkala et al., 2020)
E - (X) W| 0,
and construct an empirical dataset for X, Y.W. to perform least-square regression according to the conditional moment equation. Denote the least-square estimator of f" by f. standard analysis allows us to bound the projected Mean Squared Error (pMSE)
Y f(X) w
Ew Ex,y
Sometimes we care about the MSE of f under the population of X, Y, W, namely,
E Ex.y. (V-
We transfer pMSE MSE via the ill-posed condition (Dikkala et al., 2020; Chen & Qi, 2022; Yu et al., 2022; Uehara et al., 2022a), which is standard in the literature of the NPIV model.
G. Auxiliary Lemmas
In this section, we first introduce some lemmas that will be repeatedly used throughout the proof process.
Lemma G.1 (Freedman's 's Inequality (see, e.g., Lemma 9 of Agarwal et al. (2014))). Let (X,)== be a real-valued martingale difference sequence adapted to the filtration F,. Let E, del El. Fi] be the conditional expectation. Suppose [X,] S almost surely, then for any 0 < S 1/R it holds with probability at least 8 that
T
log(1 1/8) E [X?]
Σ
5 < Aee 2)
Σ
X
tm1
20

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Lemma G.2 (Rephrased from Theorem 1.3 of Devroye al. (2018)). For one-dimensional Gaussian distributions, we have
3 o 02
|1 142
TV (N (f) ,N (12, 02)) 2
20
20
where TV denotes the total variation distance.
Lemma G.3 (Lemma 41 of Jin et al. (2021)). Consider function class & defined on X with [6(x)] & C for all o e & and x E X, and a distribution class II over X. Suppose sequence { C and {ukJk=1 C II satisfy for all 1 E [K], Ek (e [ox]) S 3. Then for all & [K] and w >> 0, it holds that
1K
Σ pL [0.l| s0( //mpp (Viiiine (1,11, min {k, dimpe ( ()) C' + kw)
H. Missing Proofs
We provide the formal proof for Theorem 5.4 in this section. Recall that M is the aggregated model under the target distribution. Denoting the value function of any policy on M V M- we can use #* to measure the regret of any algorithm ALG as
Reg K) def V
(51)
V=" (s1),
(H.I)
where x² the policy committed by ALG in the k-tth episode.
We assume P, R, 9 are finite sets to simplify the analysis. Note that the capacity of the function space can be replaced by the corresponding covering number (Jin et al., 2021; Uehara et al., 2022b).
Before coming to the proofs, we prove some concentration lemmas at first. We define the norms of fa. E Fn
2
def
( (sh, ax)
(H.2)
2
j=1
|
def
Σ
fh
(H.3)
2.k
Let the filtration Fu be induced by {(5]. aj ef. rf. ... in ns en Fh H We can use the Freedman's inequality to bound the difference between them.
Lemma H.l. With probability at least 1 8/2, for any f {fr) any (k, E [K] x [H]. we have
11 - 1| < | + 4(e - 2 log
1
Proof. Consider the martingale difference sequence X, def R3 a/))
E
an, "d, [f ax)). Then E[X, [F-1]= 0
since T is F,-1 measurable. Moreover, |X,| 2B² almost surely.
Note that E Fj-1] < BºE sn.as d 3 [52 (sh, an)), invoke the Freedman's inequality (ef. Lemma G.1) with union bound over Fr [K] [H] to show that with probability at least 8/2 for any À 1/2B².
10g(4KH VSn, k,
|1 2 - 1 - 11
Choosing À 1/4(e- B² completes the proof.
21

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
For any 2a E (R,, R Ph,: Gh (Ph - +1 assume that have || S B. Recall the definition of the risk function and empirical risk function (see, e.g., Equations (4.3) and (4.4)), namely,
(s an an)un(sn ah, ew)]
on enp
==1
(w), =
Jn of un (8p
1=1
With a little abuse of notations, use (5 ob cqp) denote sample from 8n, On. Cn dhh"' vbs to wit,
For 1/ RR, Ri Br (5h al.. v thd (5 e2) r
For 1/ Ph, - - in (5 og. ( del GL. on ct) 5/t1,
For un (Ph- P1 Dn (sh ol, 2)) dr Pigh+1 (5/ ai. oh) - gh+1 (8/+11)
For any (k, [K] x (H] and un 2n for Vn (Rr- Rí Ph.i Gha (Ph Pi we have the following lemma
using Freedman's 's inequality.
Lemma H.2. With probability at least 1 - 8/2, for any (k, [K] x [M] and vn Vn. fh E Fr
(vn. fw) (2 fn) s 4B (BB/
+ log 6KK F())))))
Proof. Let the martingale difference be
Xj def fa (8% af (n eb)
E
sn.on ap [Jn (8h, (sn, an, en)
We know that Xyyl S 2B2 almost surely.
For fixed (k, h, Mh: Ji) tuple, observe that
Σ
EX
Fy-1] S
Σ ==1
E c a
[sa an)e S B² ||
since TT' is FF--F- Therefore, if
log (1/8)
B
11 Ve-2
2B²
holds, then
4B log(1/5)
||5
2
Invoking Freedman's inequality (cf. Lemma G.I) by X 1/2B² yields that
(gg()/)
(pn, fi) - (vn, fw) s A(e - 2)B² 1
- log(1))))))
A
Otherwise, we invoke Freedman's inequality with
0lg(1/8)
A =
<
B 5
sk]
Vc 22-2-
2B
22

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
yielding
22 2) log(1/0) (18) || (uns [b) -x) (vn, (a)
The lemma is finally proved by taking union bound over all (k, h, Vb. fr.).
Lemma H.3 (Consistent Confidence Set). Define the confidence level (1; B2, 9y in OPME by
31 28B log (
82 2 log K [H|F[PP))
(H.4)
8g B log K [H]F((/)/))
With probability at least 1 8, the confidence set Ck is consistent in that the underlying model is contained in CK, namely,
Rg E R2, Gh Ph. P% Ph, M C*,, h(), [K] x [M] [d.].
Proof. We assume the high probability events in Lemma H.1 and H.2 hold for simplicity. Note that the probability that either of them fails is at most d.
Lemma H.1 implies for any fr. E Fr
11 4(e log & || $ $2 11 + 4(e 1og
3
Consider (()) ma (1, 1/ for 1 E (R% Th P/ For any fixed fa Fh have
11.
(.(4..f))
2
11,
S Sh)
+ 4B 4B (BgK
11
S Sh)
4
+ - 10g22)211111
2(e
11
S +1B///og(//1///11//01111
+ 4B2
Here y denotes the corresponding function space R2 - Pn. G or (Pi - PB 9h+1- The first inequality is by Lemma H.2. The second inequality is due to Lemma H.l. The third inequality holds because 1h (1h.fa) O for any fr. by definition (see, e.g., Equation (4.3)).
Note that Equation (H.5) is a standard quadratic function with respect to || 2|,, we have that
1
(1,,, fn)
11 +B /
Silla + 4B² 1og(3KH + 2(e (ttp://0000+02000001000222221111 1og22(
4
28B2 log KH F
holds for any Jr. Fr. Therefore, with probability at least 1 8, for any (k) E [K] x [4]. it holds that
|1sh l2,
( = max (1h, fn)
< 28B2
log( FD1/O)
Jn
2
By the definition of B1, B2, So. we can finish the proof.
23

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability Lemma H.4. With probability at least 1 6, it holds the following statemenis.
For any (k, h) E [K] x [H] [dg] and Rs R2y Gr,s E Ph.
(
(Ben-natlinn (s an en) R2 (5hh (h =0(3))
E
O(31),
Σ
E (n
(Ben [Sn,lss axs axi en) (s, an, enl))) O(8s).
j=1
For any (k, E [K] x [H] and Pa E Ph. 9h+1 E Ght1,
(n (E [Phgh+1(5h On ex) Phigh+ (sh, Cre as. en)l)" =((3).
Proof. We assume the high probability events in Lemma H.1 and H.2 happen for simplicity. Note that the probability either of them fails is at most 6.
For any U/ { Ri Ph., Ci - pn) define function f(vn] as
fim]: S.X A I such that f/nn]ss), an) Een (Fa. (F. (un an, e)]
(H.5)
By Assumption 5.1 we know fival E Fn for any V/-
By definition, we know
(en ond (BennBit(hnawn IPn (sh, an, en))] =
12 -
f(vn))
(H.6)
The second equation holds because
(yn. f(vn)) =
an [f(un](sn, an) on, en]
j=1
Σ
Ben (aa (fl. (n) an en) sh anl]
Σ (sn.an)mds
flun](sh, and
[un an, en) sh anl
j=1
Σ
[ (ww (sn, an en)) enl))²
=
(n)
1=1
For any E 3n- = [R] -R7, Ph:
Gi (Pt Pp) and any fn we have
(vh, fn)
2 (un,
4B http://hwH.411/11///0011011111/1
|
2
2.k
3 +
+ 44B
2
311.21 12
3
5
+ 4B (BB///3333///77///)11 4B² log (o 2(e 22 (1/
4
Here 3 {3,, 3z. } is the corresponding confidence level of V/-- The first inequality is by Lemma H.2. The second inequality is due to the construction the confidence sets R/ Ph.,, Pj according to Equations (4.7), (4.8) and (D.5). The third inequality is by Lemma H.1.
24

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Plugging in Sn [(en] implies
(v%, f(vn)) = [////]*13
3 |1 4B (10003((///])))))1//) [l
S 33+
+ 4B 12
Thus have
3 + 4B | 1og
+ 2 B) (og
Solving this expression proves the result.
Now we use the ill ill-posedness measure (Definition 5.2) and knowledge transfer multiplicative term (Definition 5.3) to propose the following lemma.
Lemma H.5. With probability at least 1 8 it holds the following statements.
For any (k, h. i) E [K] x (H] (dg] and R2 R2, Gn,s E Ph
k
E
[Rn(sh, an, (hh, ah, en)) ( (o
Σ
E
(Ghh On, ex) (oll (Onnn))
(f)
For any (k, h) E [K] x [H] and Pa E Pi. gh+1 E Gut1.
(Pngh+ (an an, en) - Ph on, ex))²] = 0 0
(n)
Proof. This is straightforward application of Lemma H.4. Take the reward function an example, we have
Σ
k
(an (o (BennEEs(iennnn))) [R((nn on, en) - (sh, ah, en))
= 0
(H.7)
according to Lemma H.4.
By Equation (H.7) and the definition of The holds that
E
(R an,
an, en)
R2 (Sn, ah ex)) = 0((m))
(H.8)
By Equation (H.8) and the definition of Cf we have
k
(en. (n (Ba(sn, an, R2 (sn, an, an, en)))] =0 = (Bin.)))
The proof is identical for the rest two terms.
25

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Lemma H.6 (Regret Decomposition), Let d'-- J. (s, a) del Pr (sn = s, ab =a) be the occupancy measure of x under the unknown aggregated model M Recall that the optimistic model M -M(R p*) is defined in OPME (Algorithm 2). The regret can be decomposed
Reg PPPMOEEED, K)
Σ
V Vrr, (81) ($1)
K
H
[Rt an, Ri (sh, ahe en)
E
(oh (nh w
H
Σ
Ch (Sh en) (sn, on, an, en)
for the dynamical system transition class, or it can be decomposed as
K
Reg(OPME-G, K)
Σ ( Vaa (
K
E (sn an Iedft
an, en) - (sn, (s,, mn))
R= h=1
H
E (nn.a di
M4 (sh, Ph
PAVM Mr M4 (sh, (Sh, an, en
for the general transition class.
Proof. The regret can be decomposed as
K
K
Reg(OPME-D, K) = Σ
VE
M- (81) - V2 -vxt
M-, (81) S Σ
v
Mi (81) - D=* (81)
k=1
E
(sn, an) (7,, and + Ph ve
Mit (41h, VAV M4 (s)
sa as)
k=
(sn, an) (s,, an)
(sn (s)
do
k=1
K
|P 8hy an) Ph 8h, an) am)l
(nn
Kmm
For the transition term, we can bound it by
[|IPA (- sh. an) - -P sh an)l
(ox 0h r
K
H
P...eeeeeaaa. [Pk sns ab eny - P. sh. an. Cn tx)] ||,
(n Jatk
k=1 1=1
K
E
| sh, ahs en, (n) PT( Sho ah eh, dn)lla
(ss on) warte PewP Pww.aeeaaaa...........
k=
1=1
The first inequality uses Jensen's 's inequality. Let (: sh, an, PH) be the distribution of en under Shy ag and ty ~ P/. For the dynamical system transition class, we know Pa(:
8h, ah, Ch, (n) is diddiiensi Gaussian distribution with mean
26

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Go ubs eh) and covariance Ia (i.e., independent Gaussian random variables) by Equation (D.1). Therefore, we have
E
Mr ChrPPh ~ Ph da) ||p (- sh: on, ch, (h) Pt sh. are eb: to [1)
(sh.0n Jovd
H
[|G an en) - Gi an en ewll
(s Iod a (la.an
1
by Lemma G.2.
This term be further bounded by
K
H
E
G (sh an, an, en)
(sh
(sh, ar ]
(oh and /d sn (lma
H
G ans en)
an; Gn
on en) Jadi k=
K
H
de
E
(hh en) - (s, an))]
where the first equality is by the definition of dx (see Section 3.3) and the aggregated model Mr Similarly, the reward term can be bounded by
k
H
[1t an) R2 (sh, an)l
E (os (ok -d
E
(sh, an; an, en) Rf ah en)
(Ah (a Na
Ne
A=
H
(R an, en) (s,, as;
(h))) enll]
k=1
For the general transition class, decompose the regret
K
Reg(OPME-G.r. K)
Σ
F ($1)
VM (81) S
Σ
v
(81) - V=
k=
k=1
[Rihs an) RR 0n) + p
(st. and
Pr ve A+ (sn, an) an)
M
k=1h=1
The transition term can be bounded by
ph Weth
101 (et.11111hhh. (Sh, - V. Mr A+1 (sh, un) ]]
E lnddee
[ [eL
(pt Dat NM A4
[p
ane (he, P7 Vat Da A ah, (h.
Serch
K
pt Mr 1 ann en))
Pr Mi
M4 1 on en)
(ss. (ss.on Jadf ot
k=1k=1
The last inequality is by Jensen's 's inequality.
27

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
Now to bound the regret of OPME.
Theorem H.7. Under Assumption 5.1, with probability at least 1 ô the regret of OPME is bounded by
Reg(OPME-D,, K) = Σ
HB
for OPME-D, DD, and
H (K) Ô
(
for OPME-G.
Proof. Fix h E [H]. Since R. R for any & [K], we use Lemma G.3 with
C= B
$ = Rr Rig Ob R R M4 dia"
VK
to obtain
K
E
(on (a [| ar en) R2 an, en)
k=1
0 dimpeERR - My, 1/VK)$(m.CKKK
by Lemma H.5.
Similarly, for any E [d,), we have
(es an (sh ani en) - Gh. an, en)l
0 (Vdimee(Phs Ph II, 1/VK))/s,KKKKK
By Lemma H.6, with probability least 1 - 8, we can bound the regret of OPME-D
K
H1
Reg (OPME-D, K) S H
( an en) - (8 On, (nnen))
(sh.0h en)a
1=1
k=1
H
E
|| (Sh, an)en) - (i ans are en)ll an
Jom Am
HB ALA.A////1/////////11100110
Similarly, we invoke the Lemma G.3 with
C= B
1
$ = PP PAGh41, = P
PA
Mr d
VK"
M4,4+1
to obtain
||
p Mr (1h, Př PR (Sn, any (Sh, Cn)
1=11
( Vdimpe diimee(Phhrtt (PhOn11- P 1I, 1/VK)) 1/VK))&m,CKK)
50
28

---

The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
The regret of OPME-G is bounded as
Reg (OPME-G, K)
E
on badt
| V A (sh, ans anren)) end - Ph M A+1 (sh, an en)
V
K
H
E
(8hs ans (ns ex) - (s%, ane en (an en modth
Jmm Am1
Σ
B (
Proof of Theorem 5.4. The sample complexity of OPME (Theorem 5.4) can be obtained by standard online-to-batch conversion (Jin et al., 2018) from Theorem H.7. That, the suboptimality of a uniform policy from {Tı, T2, J& for a given number of episodes K is at most
Ô h== HB
HB
VK
for OPME-D, and
Em=
Eh=IB (o(()) F1/8)
H
Ö
VK
for OPME-G by Theorem H.7. To bound this suboptimality term to be at most can prove the theorem by setting K according to the theorem.
I. The Necessity of the Ill-posed Measure and Knowledge Transfer Multiplicative Term
Recall that the sample complexity of the model-based algorithm OPME-G has a linear dependency on the ill-posed measure The the knowledge transfer multiplicative term Cj,- and the distributional Eluder dimension dy Generally speaking, they all necessary terms in our bound in order to find near-optimal policies. Now, we discuss the necessity of these terms.
The distributional Eluder dimension is standard in the literature of RL with general function approximation (Jin et al., 2021). Without bounded distributional Eluder dimension, the sample complexity can scale linearly with the state space and action space in the worst case.
The ill- ill-posedness measure is also standard in the ill-posed inverse problems. This term is necessary as long as we hope to identify the underlying reward function R and transition function pa Taking the reward function as an example, the mean square error of identification lower bounded by the inverse of eigenvalues of an operator K, where K is defined on R2 R2 and (Kv)) an) := E,, [P% (sh, ah en. as pointed out by Chen & Reiss (201 Hall & Horowitz (2005). In other words, K is a linear mapping from the function space of (sh, 4h, en) (endogenous variables) to the function space of (sh, .n) (instrumental variables). Suppose the eigenvalues of K are X1 X2 2 2 0 and A 2 h = then the lower bound of the MSE scales as 22n (((=00((+)) (n is the number of samples) for a, B 2 0. Here a controls the magnitude of the ill-posedness measure defined in the paper, and if a - oc the estimation error will diverge even if n is very large.
The third term is the distributional shift term. Our problem is similar to the covariate shift setting in the unsupervised domain adaptation. We can regard the model as using 8h, aj: ep to predict The 8h+1 with underlying functions R2 Pj The source distribution is dh and the target distribution is d, for an arbitrary policy æ. Therefore, a well-known conditions for domain adaptation to succeed in this setting (Ben-David & Urner, 2012: 2014) the so-called weight ratio being lower bounded, which is equal to minx dt "X)) (x)/d, (X) and X is any measurable subset of the input space. That is exactly equal to the distributional shift term C₁ defined the paper up to constant multipliers. Intuitively, there will be no information being transferred to the target in the worst case without such conditions.
29


Reviews:
[{"review_id": "xZKBOZd4nz", "reviewer": "Reviewer_Whc9", "summary": "The authors consider a principal-agent problem where the principal interacts with a sequence of strategic agents with private types drawn from a different distribution than one the principal has information about. The principal's reward depends on unobserved confounders, so the authors propose using an instrumental variable technique to faithfully estimate quantities of interest, before applying variants of the sample complexity analysis for model-based RL.\n\n## Update After Rebuttal\nThe authors added in a discussion of some of the points of confusion I originally had to the paper. I already factored this into my evaluation of the paper, and hence maintain my score", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your useful comments and suggestions!\n\n**Regarding the minimax estimators for IV**: \n\nWe employ F-R duality to formulate a minimax estimator instead of using DeepIV or DFIV for the following reasons:\n\n1. Our primary objective is to design **provably sample-efficient exploration algorithms** for real-world multi-agent decision-making systems with information asymmetry and knowledge transportability. The minimax NPIV method serves as a tool to address confounding issues in our framework. Additionally, analyzing its statistical efficiency is crucial for proving the sample complexity of our exploration algorithm. While the minimax approach aligns well with our analysis, DeepIV and DFIV rely on deep neural networks, making statistical analysis challenging.\n\n2. DeepIV and DFIV follow a 2SLS framework for IV regression in linear settings. Our framework generalizes beyond the linear case, as demonstrated in Section 5.2, where we show how our setting reduces to the linear case. Consequently, a more general algorithmic framework is necessary.\n\n**Regarding the bounded Lagrangian multipliers**: The Lagrangian multipliers can be bounded because the **concentration analysis of the NPIV model does not require them to take optimal values**. We discuss the relevant bounds in Lemma H.4 (Appendix H), where we show that the desired values of the Lagrangian multipliers for the concentration analysis remain within a constant range.\n\n**Regarding the zero mean of the instrumental variable**: We will expand Example 3.1 to illustrate a specific scenario where the zero mean assumption holds. Consider a company recruiting project managers (PMs) to lead projects. The company determines PM salary levels, with states corresponding to the company's status (e.g., stock price) and actions representing salary decisions by the board. The PMs' private types can be diligent or lazy. The zero mean assumption requires the company’s reward to be approximated by an underlying reward function $R^*$ under any agent type distribution. This is reasonable because the feedback $e_h$ is able to capture the bias introduced by the agent type distribution. For example, when there are more diligent PMs, the company receives more positive feedback, leading to higher rewards with the same $R^*$ but a higher probability of positive feedback. Generally speaking, we can \"move\" the mean into the reward $R^*$ through the agent type distribution. Notably, the zero mean assumption does not require the noise to be zero mean given a specific agent type.\n\n**Regarding the experiments**: \n\n We conducted a small-scale experiment in the tabular setting, motivated by Example 3.1.\n\nA corresponding bandit setting is constructed as follows: There is a single state and $H=1$, with two candidate actions, $H$ (high salary) and $L$ (low salary). The agent’s private type $t$ can be either diligent ($d$) or lazy ($l$). The principal’s feedback, representing project performance, can be good ($G$) or bad ($B$). The reward function $R^*(a, e)$ takes as input the action $a$ and feedback $e$. The feedback distribution $F(a, t)$ is defined as follows:\n- If $a=H$ and $t=d$, the feedback is always $G$.\n- If $a=L$ and $t=l$, the feedback is always $B$.\n- Otherwise, feedback is equally likely to be $G$ or $B$.\n\nIn our experiment, we set $R^*(H, G) = 1.5, R^*(H, B) = 0, R^*(L, G) = 2, R^*(L, B) = 1$. The source agent distribution is $0.4$ for $d$ and $0.6$ for $l$, while the target distribution is $0.8$ for $d$ and $0.2$ for $l$. The principal's optimal action is $H$ for the target distribution and $L$ for the source distribution.\n\nThe empirical risk function $\\hat{L}^k$ in episode $k$ has the closed-form:\n$$\\hat{L}^k(R) = \\max_{f=(f_H, f_L)} \\sum_{\\tau=1}^k \\left(f(a_\\tau) (R(a_\\tau, e_\\tau) - r_\\tau) - \\frac{f^2(a_\\tau)}{2} \\right).\n$$\nTaking $f_H$ as an example, the closed-form solution is $\\sum_{a_\\tau = H} R(a_\\tau, e_\\tau) - r_\\tau$. The solution for $f_L$ follows similarly. To simplify, we discretize the entries of $R(a, e)$ so that each takes values from \\{0, 0.5, 1, 1.5, 2\\}, leading to $5^4 = 625$ candidate models initially.\n\nThe following table summarizes the results, illustrating the convergence of our algorithm. We ran experiments with three random seeds, using $\\beta = 600$ for 1800 episodes. In all cases, $R^*$ was successfully recovered. The reported values reflect all three seeds.\n\n| Episode    | 300 | 600 | 900 | 1200 | 1500 | 1800 |\n| -------- | ------- | -------- | ------- | -------- | ------- | ------- |\n| Remaining models (625 in total)  | 25,32,37  | 5,14,14 | 1,5,2 | 1,2,2 | 1,2,1 | 1,1,1 |\n| True action $H$ taken (percentage) |  29.7%,31.3%,27.3%  | 14.8%,15.7%,22.2% | 43.2%,16.8%,34.8% | 57.4%,37.6%,51.1% | 65.9%,50.1%,60.1% | 71.6%,53.1%,67.4% |\n\n**Regarding the presentations and references**: Thank you for your suggestions. We will revise the presentation and incorporate the recommended references accordingly.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "No experimental methods.", "theoretical_claims": "I read all the theorems and skimmed the proofs and nothing struck me as clearly false.", "experimental_designs_or_analyses": "There are no experiments, unfortunately.", "relation_to_broader_scientific_literature": "Essentially, this paper does analysis for MBRL with confounders / transportability.", "essential_references_not_discussed": "Could you add in a reference to https://arxiv.org/abs/2202.01312? I also think Chen & Pouzo '12 is the right citation for the measure of ill-posedness you consider in the paper (https://eml.berkeley.edu/~dpouzo/pdfs/cp-rate-webpage-jan-11.pdf).", "other_strengths_and_weaknesses": "At some level, this paper is a combination of several fairly well explored techniques (MBRL, instrumental variables, transportability). I think it is technically interesting to be able to combine these, but I'm not quite sure how useful / impactful this combination will be,", "other_comments_or_suggestions": "- Could you match the colors of the variables in Figure 1 and Figure 2? Also, could you use different colors for Figure 2 (i.e. having a separate color for IVs vs confounders) and add in $\\xi$ to the SCM?\n\n- I'd suggest cutting / reworking Example 3.2 -- it seems entirely disconnected from the paper.\n\n- I'd suggest adding in a simple experiment on a tabular problem -- I think this should be fairly easy to do as you could compute the discriminators / Lagrange multipliers in closed form.\n\n- I think there's a typo on lines 259-260 re: where the word \"principle\" appears in the sentence.\n\n- I think it should be \"single-policy\" concentrability in Defn. 5.3 -- do you mind checking this?\n\n- For the specific case of the game-theoretic IV algorithms, it should be fairly easy to add in computational efficiency results via the standard no-regret machinery. It might be interesting to do so to complement your statistical results.", "questions_for_authors": "1) A common critique of instrumental variable methods is that the zero mean, additive confounding assumption is unreasonable for a lot of applications. Could you comment on specific scenarios where this might be approximately true and add them to the paper?\n\n2) Why did you choose the minimax estimators for IV rather than either the \"DeepIV\" / generative modeling approaches (https://proceedings.mlr.press/v70/hartford17a/hartford17a.pdf) or the DFIV techniques (https://openreview.net/pdf?id=sy4Kg_ZQmS7)? I don't think the game-theoretic formulation is fundamental to your claims here so you might be able to instead frame your paper as a framework rather than analysis of a particular algorithm.\n\n3) You assume realizability for the discriminators your training. Loosely speaking, I think of these as being Lagrange multipliers for the vector of conditional moment restrictions. Lagrange multipliers can often need to take unbounded values to actually enforce constraints are satisfied. Could you discuss why a finite bound $B$ is a reasonable assumption?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5h1ya0ugs8", "reviewer": "Reviewer_o5zg", "summary": "This submission investigates online strategic decision-making in multi-agent environments characterized by information asymmetry and knowledge transportability. Specifically, it addresses the challenge of learning optimal decision policies when agents have private information that introduces confounding factors, and when direct experimentation in the target environment is infeasible, thus requiring knowledge transfer from another, easier-to-study domain. To tackle these issues, the authors propose an online strategic interaction model and employ a nonparametric instrumental variable (NPIV) approach for causal identification to handle confounding. Coupled with optimistic planning, their algorithm effectively transfers learned causal insights between different populations. Theoretically, the submission shows that the proposed approach achieves near-optimal policy learning with a tight sample complexity, explicitly characterizing how information asymmetry and differences between source and target domains impact learning efficiency.\n\n## update after rebuttal\n\nI read the authors' rebuttal. Although there is a slight misunderstanding in their interpretation of the cited paper, I generally agree with their revisions. I tend to maintain the current score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful comments and feedback!\n\n**Regarding the Markov policy class**: We focus on the Markov policy class because any online strategic interaction model has an **optimal Markov policy**. This follows from the fact that an online strategic interaction model is equivalent to an MDP when the agent's private type distribution is given. Please refer to Section 3.1 of the paper for further details.\n\n**Regarding the comparison with [1]**: While [1] also investigates a multi-agent generalization of the principal-agent problem, our work differs in formulation, methodology, and analysis.\n\n- **Formulation**: [1] adheres to the traditional principal-agent framework, where the principal designs an incentive-compatible signaling scheme, and the agent responds based on the state and the principal's generated signal. In their setting, the principal has an information advantage over the agent, and their rewards depend on the global state and the agent’s observable action. In contrast, our model fundamentally differs: the agent possesses private information hidden from the principal, and the agent’s unobservable private actions directly influence the principal’s reward. Additionally, both the principal and agents independently maximize their own utility functions without the incentive-compatible constraint. As a result, the decision-making processes in our model and theirs follow different logical structures.\n\n- **Methodology and Analysis**: We propose a provably sample-efficient algorithm leveraging the NPIV method and optimistic planning. Our work includes a rigorous statistical analysis establishing the sample complexity of our algorithm. In contrast, [1] adopts a policy gradient approach and provides extensive empirical evidence to demonstrate its effectiveness.\n\n**Regarding the typos**: Thank you for point out them, and we will fix them accordingly.\n\n[1]. Lin, Yue, et al. \"Information design in multi-agent reinforcement learning.\" Advances in Neural Information Processing Systems 36 (2023): 25584-25597.", "claims_and_evidence": "Clear.", "methods_and_evaluation_criteria": "#### Issue 1\nLine 123. \n> We consider the time-inhomogeneous Markov policy class $\\Pi$ in this work.\n\nWhy do you concern Markov policies rather than history-dependent policies? It would be helpful if the authors elaborate the reason. Sometimes history-dependent policies are necessary. For example, see the discussion in Section 3 of this paper:\n\n- Bernasconi, M., Castiglioni, M., Marchesi, A., & Mutti, M. (2023). Persuading farsighted receivers in mdps: the power of honesty. _Advances in Neural Information Processing Systems_, _36_, 14987-15014.\n\n#### Issue 2\n\nFigure 1 illustrates the timeline of their proposed model. This model specifies the focused problem. But it is very similar to the Markov signaling game proposed in the following paper:\n- Lin, Y., Li, W., Zha, H., & Wang, B. (2023). Information design in multi-agent reinforcement learning. _Advances in Neural Information Processing Systems_, _36_, 25584-25597.\nEspecially the extensions mentioned in it. So it would be helpful if the authors provide the comparison between them.", "theoretical_claims": "No.\n\nThis is an emergency review task for me. I only saw the invitation two hours before the deadline, so it was impossible for me to review it thoroughly.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The author's discussion in the related work section is relatively comprehensive.", "essential_references_not_discussed": "Mentioned before.\n- Bernasconi, M., Castiglioni, M., Marchesi, A., & Mutti, M. (2023). Persuading farsighted receivers in mdps: the power of honesty. _Advances in Neural Information Processing Systems_, _36_, 14987-15014.\n- Lin, Y., Li, W., Zha, H., & Wang, B. (2023). Information design in multi-agent reinforcement learning. _Advances in Neural Information Processing Systems_, _36_, 25584-25597.", "other_strengths_and_weaknesses": "Provided examples in Section 3 are helpful.", "other_comments_or_suggestions": "- \"casual\" should be \"causal\" in several places.\n- \"confounded\" is a bad word. I suppose it should be \"confounding\".\n- Figure 1 and 2 are too big.", "questions_for_authors": "Mentioned before.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p3yOetDA8Z", "reviewer": "Reviewer_6m6G", "summary": "This work considers a principal-agent RL framework, where the reward and transitions also depend on the unobserved action.\n\nIn this framework, the authors propose an algorithm that will learn the principal rewards, but also --- and this is the challenging part because of the fact that only partial, cofounding observations are available on the agent action --- the agent reward and transition probabilities. For that they use knowledge transfer methods, and derive a sample complexity upper bound for their algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions!\n\n**Regarding the limitations of standard online RL algorithms in our framework**: The core reason standard online RL algorithms cannot be directly applied is that the online strategic interaction model under the source agent distribution (denoted by $\\mathcal{M}^*(\\mathcal{P}^s)$) differs from the one under the target agent distribution (denoted by $\\mathcal{M}^*(\\mathcal{P}^t)$). Simply ignoring feedback will lead to model misspecification and linear regret, as the existence of confounders leaves you a wrong distribution when calculating $\\bar R^*$ and $\\bar P^*$. Below, we provide a detailed explanation of this distinction and why it arises.\n\nThe knowledge transportability framework in this paper requires the principal to explore the optimal policy of an online strategic interaction model when interacting with a different agent type distribution than the one used for online data collection. Since the model under the source agent distribution $\\mathcal{M}^*(\\mathcal{P}^s)$ (which can also be viewed as an MDP per Section 3.1 of the paper) **is not the same as** the model under the target agent distribution $\\mathcal{M}^*(\\mathcal{P}^t)$, standard online RL algorithms cannot be used to find the optimal policy for $\\mathcal{M}^*(\\mathcal{P}^t)$.\n\nA key motivation for studying knowledge transportability is that the agent population with which the principal interacts may change over time. For example, the personal attributes of job applicants at a company can vary across different periods. To capture such scenarios, our model allows the agent type distribution during the online interactions to differ from the target. We also provide Example 3.2 in the paper as a motivating illustration.\n\nIf the source and target agent populations were **identical**, standard online RL algorithms could be directly applied. However, when the populations differ, solving the problem becomes considerably more challenging.\n\n**Regarding the experiments**:\n\nWe conducted a small-scale experiment in the tabular setting, motivated by Example 3.1. Consider a company (the principal) is recruiting project managers (PMs, the agents), and the company needs to determine the salary of the PMs. \n\nA corresponding bandit setting is constructed as follows: There is a single state and $H=1$, with two candidate actions, $H$ (high salary) and $L$ (low salary). The agent’s private type $t$ can be either diligent ($d$) or lazy ($l$). The principal’s feedback, representing project performance, can be good ($G$) or bad ($B$). The reward function $R^*(a, e)$ takes as input the action $a$ and feedback $e$. The feedback distribution $F(a, t)$ is defined as follows:\n- If $a=H$ and $t=d$, the feedback is always $G$.\n- If $a=L$ and $t=l$, the feedback is always $B$.\n- Otherwise, feedback is equally likely to be $G$ or $B$.\n\nIn our experiment, we set $R^*(H, G) = 1.5, R^*(H, B) = 0, R^*(L, G) = 2, R^*(L, B) = 1$. The source agent distribution is $0.4$ for $d$ and $0.6$ for $l$, while the target distribution is $0.8$ for $d$ and $0.2$ for $l$. The principal's optimal action is $H$ for the target distribution and $L$ for the source distribution.\n\nThe empirical risk function $\\hat{L}^k$ in episode $k$ has the closed-form:\n$$\\hat{L}^k(R) = \\max_{f=(f_H, f_L)} \\sum_{\\tau=1}^k \\left(f(a_\\tau) (R(a_\\tau, e_\\tau) - r_\\tau) - \\frac{f^2(a_\\tau)}{2} \\right).\n$$\nTaking $f_H$ as an example, the closed-form solution is $\\sum_{a_\\tau = H} R(a_\\tau, e_\\tau) - r_\\tau$. The solution for $f_L$ follows similarly. To simplify, we discretize the entries of $R(a, e)$ so that each takes values from \\{0, 0.5, 1, 1.5, 2\\}, leading to $5^4 = 625$ candidate models initially.\n\nThe following table summarizes the results, illustrating the convergence of our algorithm. We ran experiments with three random seeds, using $\\beta = 600$ for 1800 episodes. In all cases, $R^*$ was successfully recovered. The reported values reflect all three seeds.\n\n| Episode    | 300 | 600 | 900 | 1200 | 1500 | 1800 |\n| -------- | ------- | -------- | ------- | -------- | ------- | ------- |\n| Remaining models (625 in total)  | 25,32,37  | 5,14,14 | 1,5,2 | 1,2,2 | 1,2,1 | 1,1,1 |\n| True action $H$ taken (percentage) |  29.7%,31.3%,27.3%  | 14.8%,15.7%,22.2% | 43.2%,16.8%,34.8% | 57.4%,37.6%,51.1% | 65.9%,50.1%,60.1% | 71.6%,53.1%,67.4% |\n\nWe hope our rebuttal has clarified the reviewer’s confusion and respectfully hope that the reviewer would consider re-evaluating the merit of our work accordingly.", "claims_and_evidence": "see below", "methods_and_evaluation_criteria": "see below", "theoretical_claims": "see below", "experimental_designs_or_analyses": "see below", "relation_to_broader_scientific_literature": "see below", "essential_references_not_discussed": "see below", "other_strengths_and_weaknesses": "see below", "other_comments_or_suggestions": "My main concern with this work is that it is based on the claim that the considered framework \"is more challenging than classic RL\". I however disagree with this claim, as we could still apply any RL algorithm to that framework, ignoring the agent feedback and intervention. \nIndeed, the principal could just learn using the marginal rewards $\\bar{R}^*$ and transitions $\\bar{P}^*$.\n\n$e_h$ seems to only correspond to additional feedback (wrt to classical RL framework), that can enhance learning, through a learning of the agent reward functions (and transition). But then, I would like more convincing results towards the fact that the proposed algorithm and derived bounds yield some improvement wrt typical RL algorithms. Notably, the sample complexity bound of Theorem 5.4 seems to be similar to the typical one in RL, if we omit the dependency in the number of states. Here is the number of states does not appear, but might be hidden into new terms such as the $\\mathcal{R}$ or $\\mathcal{P}$. \n\nAs a consequence, I would like to have a concrete example by the authors (e.g., if the reward class for the agent is linear) that clearly yields an improvement in terms of sample complexity with respect to typical RL bounds. Additionally, some experiments might be helpful.\n\nCurrently, I feel that the algorithm might learn unnecessary things, such as $R^a$ and $P$, while learning $\\bar{R}^*$ and $\\bar{P}^*$ should be much simpler and competitive.", "questions_for_authors": "- Why couldn't we apply typical RL algorithms to your framework, with the suggestion made above?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bfb5v7tMbF", "reviewer": "Reviewer_Ju5y", "summary": "This paper studies online decision-making under information asymmetry and knowledge transportation. They formulate this problem using strategic MDP where an principle interacts with a sequence of myopic agents whose can impact the reward functions and transition kernels. The goal is for the principal to design a near-optimal policy that maximizes its total rewards when interacting with a target population of agents that might be different from the source population of agents during learning. The paper proposes a model-based algorithm that uses nonparametric instrumental variable method which can learn $\\eps$-optimal policy using $O(1/\\epsilon^2)$ samples.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments and suggestions!\n\n**Regarding the technical novelty compared to [1]**: In contrast to Yu et al. [1], this work studies the **online** strategic interaction model. Below, we briefly highlight the key technical novelties, with further details provided in Appendix B.3.\n\n1. To better align with real-world scenarios, our online model explicitly incorporates knowledge transportability. A key motivation for this is that the agent population with which the principal interacts may evolve over time. For example, the personal attributes of job applicants for a company may vary across different periods. Thus, our model allows the agent type distribution in the online setting to differ from the target agent type distribution of the principal.\n\n2. The online strategic interaction model **cannot be directly solved using standard online RL algorithms** due to endogenous noise (i.e., confounding variables) and the knowledge transportability challenge. This work introduces novel techniques to address these issues:\n\n   - While both this work and [1] leverage the NPIV model for estimating the empirical risk function $\\hat{L}$, we construct a distinct confidence set with a different concentration analysis. Specifically, [1] derives a concentration bound under an i.i.d. dataset assumption, whereas our work handles non-i.i.d. data. Furthermore, [1] constructs the confidence set by bounding the value difference between a candidate model and the minimizer of $\\hat{L}$, whereas we construct our confidence set solely by bounding the value of $\\hat{L}$ for candidate models.\n   \n   - We establish a key error propagation technique from the NPIV estimator’s error to the online regret using martingale concentration analysis with Freedman’s inequality.  Furthermore, we have developed cleaner proofs that rely **only** on the realizability assumption and the boundedness of zeros of a concave quadratic function, thereby simplifying the complex proof techniques in [1] that were based on the symmetric and star-shaped assumption.\n\n**Regarding the transferability assumption**: Knowledge transportability is considered for two main reasons. First, in many real-world applications, the principal interacts with a diverse or evolving agent population, making this assumption highly practical. Our algorithm can also accommodate scenarios where the source population $\\mathcal{P}^s$ changes across different episodes. Second, if the source agent population were identical to the target agent population, standard online RL algorithms could be directly applied. However, when these populations differ, solving the problem becomes significantly more challenging.\n\nAs for the \"worst-case density ratio over all policies $\\pi$ and distributions $\\nu$\", we note that this assumption can be generalized to an upper bound on the ratio of occupancy measures $$\\frac{d^{\\pi, s}_h}{d^{\\pi, t}_h}$$ \n\nfor any policy $\\pi$. Equivalently, it corresponds to bounding the density ratio of the agent type distribution, $\\prod_{i \\leq h} \\mathcal{P}^s_i / \\prod_{i \\leq h} \\mathcal{P}^t_i$. Ensuring this ratio remains bounded is crucial for addressing distributional shifts between the source and target populations. Our problem is analogous to the covariate shift setting in unsupervised domain adaptation, where the model uses $(s_h, a_h, e_h)$ to predict $(r_h, s_{h+1})$ based on underlying functions $R^*_h$ and $P^*_h$. The source distribution is $d^{\\pi,s}_h$, and the target distribution is $d^{\\pi,t}_h$ \n\nfor any policy $\\pi$. A well-established condition for successful domain adaptation [2,3] requires a lower-bounded weight ratio, defined as $\\min_{X} d^{\\pi,s}_h(X) / d^{\\pi,t}_h(X)$ for any measurable subset $X$ of the input space. This precisely corresponds to the distribution shift term $C^f_h$ in our paper, up to constant multipliers. Intuitively, without such conditions, knowledge transfer to the target domain would be infeasible.\n\nWe hope our rebuttal has clarified the reviewer’s confusion and respectfully hope that the reviewer would consider re-evaluating the merit of our work accordingly.\n\n[1]. Yu, Mengxin, Zhuoran Yang, and Jianqing Fan. \"Strategic decision-making in the presence of information asymmetry: Provably efficient rl with algorithmic instruments.\" arXiv preprint arXiv:2208.11040 (2022).\n\n[2]. Ben-David, Shai, and Ruth Urner. \"On the hardness of domain adaptation and the utility of unlabeled target samples.\" International Conference on Algorithmic Learning Theory. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.\n\n[3]. Ben-David, Shai, and Ruth Urner. \"Domain adaptation–can quantity compensate for quality?.\" Annals of Mathematics and Artificial Intelligence 70 (2014): 185-202.", "claims_and_evidence": "I am completely unfamiliar with this problem setting, thus cannot judge the soundness of the theoretical claims in this paper.", "methods_and_evaluation_criteria": "I am completely unfamiliar with this problem setting, thus cannot judge the soundness of the proposed method in this paper.", "theoretical_claims": "I am completely unfamiliar with this problem setting, thus cannot judge the correctness of any proofs for theoretical claims in this paper.", "experimental_designs_or_analyses": "This is a theory paper without any experimental results.", "relation_to_broader_scientific_literature": "The paper seems to discuss related works quite well by mentioning RL with confounded data, especially the discussion of Yu et al 2022 which considers a similar problem to the present paper yet in the offline setting instead of the online setting.", "essential_references_not_discussed": "The paper seems to discuss all relevant essential references to my best educated guess.", "other_strengths_and_weaknesses": "Strength: \n\n- The paper seems to study an important problem of decision making in information asymmetry and information transportability. \n\n\nWeaknesses: \n- It's hard to follow the results in the paper, especially for those who are not familiar with the literature. \n- I am not sure what technical novelty of the present paper compared to the algorithmic results and development in Yu et al 2022. I know the present paper considers an online setting instead of the offline setting of Yu et al 2022. Does generalize to the online setting require standard tools? \n- To address transferability, the paper relies on an extremely stringent notion -- the worst-case density ratio -- worst case over all policy $\\pi$ and $\\nu$. First, this density ratio can be extremely large. In fact, most of the recent algorithmic developments in offline RL does not use the worst-case density ratio any more. Second, transferability under the worst-case density ratio looks trivial. Why would we consider transferability at all if the solution offered is trivial? Why don't focus on the core problems with meaningful results?", "other_comments_or_suggestions": "I don't have any specific suggestions or comments.", "questions_for_authors": "Please address my questions in the weakness section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: We had a fruitful discussion about this paper. Overall the sentiment was rather positive (3 weak accepts, and 1 weak reject from a reviewer which is less familiar with the topic). I think our general assessment is well summarized by Reviewer Whc9, who writes "At some level, this paper is a combination of several fairly well explored techniques (MBRL, instrumental variables, transportability). I think it is technically interesting to be able to combine these, [but it also not ground breaking]".

Nitbit: The paper is partially motivated by the generalized principal-agent problem (Myerson 1982), and explicitly mentions "contract design" as a motivation, but fails to cite any of the rapidly emerging literature on "algorithmic contract theory" (esp. on sample complexity and typed agent settings).
Decision: Accept (poster)