Learning to Make Adherence-aware Advice

We thank the reviewer for taking the time to read our paper and for all the comments. Below are our responses to the raised questions.

Two testbeds of the Flabby Bird domain and the Car Driving domain:

• Sorry for the confusion. We mentioned in line 2 on page 8 that we defer the second experiment on Car Driving to the end of the appendix.

Expanding the "Theoretical reinforcement learning" section:

• We thank the reviewer for the suggestion. We presented the connection with theoretical reinforcement learning in the section Main Result, where we explained two informal theorems and discussed the connection and difference between the existing literature in detail. We believe that delving into technical details in the literature review section would be a bit too early, as by that time we haven't yet introduced the model and setting, which are critical in understanding the technical differences.

• Moreover, we'd like to point out that the contribution of this work is beyond the sample complexity bound from theoretical reinforcement learning. Rather, the primary intention for the paper is to develop a new human-AI model for the sequential decision-making context and to derive algorithmic and theoretical insights for this new problem. The main motivation for the theoretical part is that we want to showcase the structural insights of the model (we can learn the model effectively by leveraging the adherence level), and connections for related areas (reward-free exploration and provably solving constrained MDP).

More intuition for Equation (5):

• We are happy to provide more explanation about the intuition of Equation (5). For theoretical online Reinforcement Learning algorithms, they usually maintain an uncertainty measure for every $(s,a)$ (state-action) pair and behave optimistically based on the uncertainty sets. Then, on page 6, we state that "The algorithm iteratively minimizes an upper bound defined by (5) which measures the uncertainty of a state-action pair, and the upper bound shrinks as the number of visits for the state-action pair increases. The algorithm stops when the upper bound is less than a pre-specified threshold."

• Most theoretical RL algorithms include constants in the algorithm that may appear as "magic numbers". The rationale behind these numbers often originates from a series of mathematical inequalities that drive the derivation of the sample complexity/regret bounds.

We thank the reviewer again for reading our work and for all the helpful suggestions. And we hope the clarifications help to address the reviewer's concerns/confusion. In the following week, we will get back timely for any follow-up questions.

We thank the reviewer for the comments. We refer to the general response above for clarification on the positioning of our paper, and we respond to the reviewer's questions in the following.

• Regret bounds: In the informal version of Theorem 1 on page 4, we mention that $O(H^2S^2A/\epsilon^2)$ is a PAC (probably approximately correct) sample complexity bound, which is different from the sample complexity bound $O(H^3SA/\epsilon^2)$ of Algorithm 3 (in line 32 and page 4, for Algorithm 3 we use sample complexity instead of PAC sample complexity. This type of sample complexity without PAC is also known as the sample complexity for BPI (best policy identification)). For more details of how PAC sample complexity and sample complexity differs, we refer to the statement of Theorem 1 and Theorem 2.

-- In fact, to have a more comparable result to the sample complexity of $O(H^3SA/\epsilon^2)$ in Algorithm 3, we can just apply UCB-VI (Azar et al., 2015) to the machine's MDP (introduced in page 2), by the well-known trick that turns regret bound into sample complexity for BPI, and one will get the same sample complexity bound of $O(H^3SA/\epsilon^2)$ as in Algorithm 3. Notice that by simply doing this, there is no extra performance gain because neither Algorithm 3 nor this UCB-VI leverages the structure of the model.

-- A natural question is why we mention Algorithm 3 for $\mathcal{E}_2$ instead of UCB-VI for $\mathcal{E}_2$ given that they have the same sample complexity. This is because Algorithm 3 comes from Algorithm 2, which aims to solve the reward-free exploration (RFE) problem instead of BPI. Therefore, Algorithm 3 is a more well-rounded algorithm and it can also perform RFE given more episodes (see Theorem 2), while UCB-VI is not designed for RFE.

-- We believe that by leveraging the inherent property of our human-AI interaction model, one can tweak the parameters of Algorithm 1 and have a $O(H^2SA/\epsilon^2)$ sample complexity bound for BPI, and that would be more efficient than $O(H^3SA/\epsilon^2)$ of Algorithm 3 and UCB-VI. However, we choose to derive a better PAC sample complexity bound because the PAC sample complexity bound is a stronger result than the sample complexity bound for BPI.

• The proof of Algorithm 3. We apologize for the caused confusion. The proof of Algorithm 3 starts from the last paragraph of page 18. We prove key lemmas for Algorithm 3 and use them to show the similar bound in Algorithm 2. This is because the only difference between Algorithm 2 and Algorithm 3 is that the terminating threshold for Algorithm 2 is $\epsilon/(2H)$ and for Algorithm 3 is $\epsilon/2$. The sample complexity for Algorithm 3 is $O(H^3SA/\epsilon^2)$, and for Algorithm 2 is $O(H^5SA/\epsilon^2)$. The extra $H^2$ comes from changing $\epsilon/2$ by $(\epsilon/2H)$ (which is also mentioned in lines 7 and 8 on page 20).

• More explanations of Eq. (1). We gave some interpretation of Equation (1) on page 2 (above Definition 1). The first equation in (1) comes from our statement that if the machine chooses to defer, the human follows the default policy $\pi^\text{H}$. The second equation in (1) comes from our statement that If the machine chooses to advise, the human takes the machine’s advice with probability $\theta(s,a^{\text{M}})$. The third equation comes from the fact that if the human agent chooses not to adhere to the machine's advice (this happens with probability $1-\theta(s,a^{\text{M}})$, which is defined as the adherence level), the human will follow its fixed human policy $\pi_h^{\text{H}}(\cdot|s)$. However, because $a^{\text{M}}$ is already suggested by the machine and the human agent chooses not to adhere, the resulting policy will have support on $\mathcal{A}/\{a^{\text{M}}\}$ with distribution $\pi^{H}_h(\cdot|s)/(1-\pi_h^{\text{H}}(a^{\text{M}}|s))$ (we divide by $(1-\pi_h^{\text{H}}(a^{\text{M}}|s))$ to normalize the distribution).

Lastly, we'd like to thank the reviewer again for all the questions raised by the reviewer. We will clarify these aspects in future versions of our paper. In the following days, we look forward to follow-up discussions, and we will get back to further questions timely.

We thank the reviewer for spending time reading our paper, and for all the comments.

We understand that this might be a last-minute/urgent review assignment for the reviewer, so we do appreciate all the comments and suggested references (we will include these in the future version of our paper). However, we believe the evaluation/criticism of a work on machine learning/deep learning should not be solely based on the experiments, but also on a large scope covering the modeling and theoretical contributions. To this end, we have created a TL;DR version of our positioning and contribution as in the general response. And we would really appreciate it if the reviewer could spend a bit more of time on reading these corresponding parts and evaluating these aspects of our paper, and in the following week, we are happy to address any follow-up comments/questions.

In the following, we address the raised questions by the reviewer:

"Does this method handle higher-dimensional environments or continuous action spaces?"

• First, we note that we are presenting a model, not only a method. The model aims to provide a theoretical foundation so that it will be compatible with different extensions. To incorporate higher-dimensional environments, our model is compatible with the existing theoretical analyses of learning methods involving linear function approximation of the state space which provide a solution for high dimension environments. For continuous action space, we have to develop a continuous model separately. Just like the case in generic RL, the related theoretical property for continuous action is similar to the discrete one but it is out of the current scope of this work.

"How does this method handle more complex adherence functions?"

• We first note that the proposed model can be naturally related to other theoretical extensions to solve the aforementioned problem. If the adherence is nonstationary, the problem can be solved by learning the adherence level at every time step, which is a standard extension for RL algorithms. If the adherence level changes from episode to episode, we can rely on a standard approach by introducing a variational budget (Besbes, et. al. 2014) for the adherence level over episodes and get the corresponding theoretical result. If the variation of human adherence level exceeds the variational budget, the corresponding decision-making problem remains an open problem for the general theoretical RL/online learning community.

"How does this method handle co-adapting advice takers?"

• As we understand, co-adapting means that through interaction, the human will adapt to the machine and change its behavior policy or adherence level. This corresponds to a learning problem where the underlying MDP is changing, and if we are not controlling the amount of change in the behavior policy/adherence level, there is no model/algorithm that can provide theoretical guarantees for the co-adapting setting. We understand that some data-driven methods without theoretical guarantees can be very effective and practical for this scenario. We agree with the reviewer that this is an important future direction, and we will discuss this point more in the future version of our paper.

Models and high-dimensional extensions: We appreciate the suggestions on extending the result to higher dimensions. We will mention this as a potential direction for future work.

Empirical Experiment vs Numerical Experiment: We agree that experiments in a more practical setting are important. However, these experiments sometimes cannot be explained by any model or theory. In this work, if we conduct empirical experiments as suggested, it will be detached from our model because these scenarios are not related to our model at all. Instead, simpler experiments can either corroborate the underlying theory or be explained by it, making our work more sound. Furthermore, to ensure a more concise presentation of our paper, it is sensible to conduct experiments that are more closely related to our theoretical framework.

We thank the reviewer again for the time spent reading our paper. We look forward to follow-up discussions.