The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability

We sincerely appreciate your valuable comments and suggestions!

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.

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

2. 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:

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

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

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.

As 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}$

for 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$

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

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

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

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

[3]. Ben-David, Shai, and Ruth Urner. "Domain adaptation–can quantity compensate for quality?." Annals of Mathematics and Artificial Intelligence 70 (2014): 185-202.

We sincerely appreciate your valuable comments and suggestions!

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.

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

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

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

Regarding the experiments:

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

A 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:

• If $a=H$ and $t=d$, the feedback is always $G$.
• If $a=L$ and $t=l$, the feedback is always $B$.
• Otherwise, feedback is equally likely to be $G$ or $B$.

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

The empirical risk function $\hat{L}^k$ in episode $k$ has the closed-form:

Taking $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.

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

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

We appreciate your insightful comments and feedback!

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.

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.

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

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

Regarding the typos: Thank you for point out them, and we will fix them accordingly.

[1]. Lin, Yue, et al. "Information design in multi-agent reinforcement learning." Advances in Neural Information Processing Systems 36 (2023): 25584-25597.

Thanks for your useful comments and suggestions!

Regarding the minimax estimators for IV:

We employ F-R duality to formulate a minimax estimator instead of using DeepIV or DFIV for the following reasons:

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

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

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.

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.

Regarding the experiments:

We conducted a small-scale experiment in the tabular setting, motivated by Example 3.1.

A 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:

• If $a=H$ and $t=d$, the feedback is always $G$.
• If $a=L$ and $t=l$, the feedback is always $B$.
• Otherwise, feedback is equally likely to be $G$ or $B$.

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

The empirical risk function $\hat{L}^k$ in episode $k$ has the closed-form:

Taking $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.

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

Regarding the presentations and references: Thank you for your suggestions. We will revise the presentation and incorporate the recommended references accordingly.