Learning to Make Adherence-aware Advice
Authors: Guanting Chen
Xiaocheng Li
Chunlin Sun
Hanzhao Wang
Venue: ICLR 2024 poster (2024)
Keywords: Human-AI interaction
Reinforcement Learning
Primary area: reinforcement learning
TL;DR: This paper provides models and algorithms that analyze the optimal advice policy, taking into account the possibility that humans might distrust the advice.

Abstract: As artificial intelligence (AI) systems play an increasingly prominent role in human decision-making, challenges surface in the realm of human-AI interactions. One challenge arises from the suboptimal AI policies due to the inadequate consideration of humans disregarding AI recommendations, as well as the need for AI to provide advice selectively when it is most pertinent. This paper presents a sequential decision-making model that (i) takes into account the human's adherence level (the probability that the human follows/rejects machine advice) and (ii) incorporates a defer option so that the machine can temporarily refrain from making advice. We provide learning algorithms that learn the optimal advice policy and make advice only at critical time stamps. Compared to problem-agnostic reinforcement learning algorithms, our specialized learning algorithms not only enjoy better theoretical convergence properties but also show strong empirical performance.

Published as a conference paper at ICLR 2024
LEARNING TO MAKE ADHERENCE-AWARE ADVICE
Guanting Chen', Xiaocheng LiP, Chunlin Sun", Hanzhao Wang*
Department of Statistics and Operations Research, UNC-Chapel Hill
2 Imperial College Business School, Imperial College London
3 Institute for Computational and Mathematical Engineering, Stanford University guantingéung weteennc.dd edu (xiaocheng. .i,, h. wang19 9 @imperiall aac.r..ukl.... chunlin@stanf edu
ABSTRACT
As artificial intelligence (AI) systems play an increasingly prominent role in human bocision-making, challenges surface in the realm of human-Al interactions. One challenge arises from the suboptimal AI policies due to the inadequate consideration of humans disregarding AI recommendations, as well as the need for AI to provide advice selectively when it is most pertinent. This paper presents sequential eecision-makiinn model that (i) takes into account the human's 's adherence level (the probability that the human follows/rejects machine advice) and (ii) incorporates a defer option so that the machine can temporarily refrain from making advice. We provide learning algorithms that learn the optimal advice policy and make advice only at critical time stamps. Compared to problem-agnosee reinforcement learning algorithms,, our specialized learning algorithms not only enjoy better theoretical convergence properties but also show strong empirical performance.
INTRODUCTION
Artificial intelligence (Al) has achieved remarkable success across various aspects of everyday life. However, crucial to acknowledge that many of Al's accomplishments have been developed as fully automatic systems (Mnih et al., 2015] Silver et al.) 2017). In several important domains like Al-assisted driving (Balachandran et al. (021) and Al-assisted healthcare (Shaheen, (022I) Al is faced with the challenge of interacting with humans (Mozannar and Sontag 2020 De et al. (021). introducing a more intricate and demanding dynamic. This interaction between Al and humans gives rise to two significant issues. Firstly, it is common for humans reject following Al's advice, and Al assumes humans' perfect adherence to its advice, the advice generated under this assumption may not be optimal. Secondly, humans may prefer Al to refrain from constant advice-giving, opting for AI intervention only when necessary. They may value their autonomy when performing well but expect AI guidance during critical moments or when they encounter situations which they are typically less proficient. These considerations underscore the importance of comprehending human behavior and preferences to develop effective and adaptable AI systems for human-Al interactions.
To address the mentioned challenges. in this paper, we provide a decision decision-making making model for human- Al interactions. For the first challenge, the model takes into account the human's 's adherence level, defined as the probability that the human takes the Al's advice. This allows the machine to account for variations in human adherence level when making advice. For the second challenge, the Al model features action named defer, which refrains from giving advice humans. This feature recognizes that there are instances when humans prefer autonomy and only seek AI guidance during critical moments situations where they typically struggle. By integrating the adherence level and action deferral into our model, we formulate these challenges as a decision- makiin problem.
To cater to this specialized decision-making model, have developed tailored learning algorithms that are both provably convergent and empirically efficient. These algorithms are specifically designed to effectively handle the unique characteristics and challenges of the human-Al AI interaction setting.

---

Published as a conference paper at ICLR 2024
1.1 RELATED WORK
Human-AI interactions. Human-AI interactions have long been studied in fields such as robotics.
Methods for modeling human behaviors and collaborating with robots (Bobu et al. 2020 Laidlaw and Dragan 2022] Carroll et al. 2019) have achieved strong empirical performance. Similar to our definition of adherence level. a stream of literature (Chen et al.) 2018 8 Williams et al. 2023)
integrates trust (Khavas et al. 2020) as latent factors into the human-Al Al model and solves Partially Observable Markov Decision Process (POMDP) to get policies with strong empirical outcomes. Our work primarily centers on modeling and establishing theoretical foundations for the human-Al interaction model and the associated learning problems, thereby complementing the existing body of human-Al interaction literature.
Modeling human-Al interactions. On the modeling side, GGraddCCéémed and Pauphilet (2022)
propose the Eerision-makingg model that incorporates the adherence level and illustrates that when the adherence level is low, the optimal advice be different from the optimal decision. Also, Sun et al. 2022) for an applied setting of interacting with different adherence levels, [Shani et al. (2019) for the relationship between the model and the exploration-consetie
RL setting, and Jacq ct al. (222)) for the so-called lazy-MDP that features an action similar to defer in our setting.
Machine learning in human-Al interactions. Although there has been no literature associated
with learning the decision decision-making model similar to Grand -Cenn-C and Pauphilet (2022) and Jacq
al. (2022), other machine learning approaches have been put forward (Bastami al. 202 Meresht
et al. 2020, Straitouri et al., 2021 Okati et al. 2021 Chen et al. 2022 Hong et al. 2023 Mao et al.
2023
Mohri al. 2023) with different human-Al interaction settings.
Theoretical reinforcement learning. Our first proposed algorithm is an optimism- based re-
inforcement learning method that learns the optimal advice policy. This approach inspired by the theoretical online reinforcement learning literature (Jaksch et al. 2010 Lattimore and Hutter
2014. Dann and Brunskill] 2015; Azar et al.] 2017 Dann et al. 2017 Zanette and Brunskill] 2019)]
Domingues et al. 2021). Instead of directly applying the upper confidence bound in the literature, we customize the learning algorithm so that it leverages special properties in our decision making model, resulting in advantages in theoretical properties and empirical performance. Our second algorithm adopts a reward-free exploration (RFE) approach (Jin et al.) (2020). which first explores the environment for a given number of episodes, and then becomes capable of outputting near-optimal policy for any bounded reward functions. We find this approach works well for learning algorithms
that make pertinent advice. See Zhang al. [2020); Kaufmann al. (202T) Ménard et al. 2201 Miryoosefi and Jin (2022) for the follow-up works in RFE.
Our contribution is twofold:
First, we propose decision decision-making model for advice-giving that incorporates human's 's adherence level and an option for the AI defer the advice and trust the human. This is a comprehensive modeling framework for effective human-AI interactions, where the optimal decision decision-making not only considers human adherence level but also makes advice/recommendtioos only critical states.
Second, based on this decision decision-making model, we develop tailored learning algorithms that output near-optimal advice policies and know when to make pertinent advice. Compared to the state-of-the- art pooblem-agnostic RI. algorithms, our algorithm features tighter sample complexity bound and stronger empirical performance.
2
MODEL SETUP
Consider a human decision-maker that takes sequential actions under episodic Markov decision process (MDP) described by the tuple R = (S, A, H. r) The superscript emphasizes the human's involvement in this MDP, S denotes the set of states, AA denotes the set of actions, H/ is the horizon of each episode (different from the superscript H), denotes a deterministic time-dependent transition kernel so that (s'' (s a) is the transition probability from state E S to state s' S under the action a E A at time h, and r denotes a deneddepnndent reward function where T (s, a) E 1]. Let S = [S] and A |.4] denote the cardinality of S and A, respectively.
2

---

Published as a conference paper at ICLR 2024
Suppose the human follows fixed (suboptimal) policy л" such that the probability of taking action a at state s and time h is Th, (a]s). Alongside the human, an intelligent machine makes advice as decision support to improve the reward collected under T In other words, the machine does not seek to change human policy but rather improve its final outcome given its suboptimality. Specifically, upon the arrival each state, the machine superscript M stands for the machine), or to trust the human and defer the action to the human, denoted by ax defer. If the machine chooses defer, the human follows its default policy n If the machine chooses to advise, the human takes the machine's 's advice with probability ((s, a²) E [0. 1]. where ((,,) .) is the adherence level of the human, and is defined follows.
choose make advice a" E A to the human (the
Definition 1 The human's 's adherence level 0 S x A + [0, 1] is the probability of human adopt- ing/adhering to the machine's 's certain advice at a certain state.
Given the setup, the human takes action a according to the following law:
(als),
if a" = defer,
a(s,a"),
if am defer and am (adhere),
[a = als,a")=
x 1- (a
(1-0 (1-0(s, ((),a)))
if ax & defer and + am (not adhere).
To summarize, under the human-machine interaction, the underlying dynamic becomes
machine makes udvice
a P-(o.nd))
H th+1 ~ pa (n o²), 8h+1-
8h
At each time h, the machine first makes the advice " upon the state and the human incorporates the machine advice into final action a", and then transit to the next state $1+1-
The machine's 's MDP. From the machine's 's perspective, the MDP is slightly different from the MDP faced by human. It can be deseribed by M AH, ,²)). This MDP shares the same state space and horizon H the human MDP AM. The action space is augmented to include the defer option A = A U {defer]. In the machine's 's perspective, the transition can be viewed as a direct consequence of making advice a² E Å (i.e, 8h. - a" - 8h+1), and the transition kernel becomes
(s ss am) = E Pn(s'lss d²) PA aa")
a"EA
where ph is the transition kernel the MDP M and the probability [P,(- a) is specified by the adherence dynamics (T. In parallel, define the reward by marginalizing human's 's action
Mss a")
Σ (n a*) Pr (a a"EA
Denote π = heew the machine's policy where m. S - A. The value function then becomes
H
Vig (s) E
(sn, an) smo = where ag = =T((s)) and 8h+1 ~ (- an);
ho
and V = for any s E S. The optimal value V and the optimal policy x" are defined by (i(s)
max (s), x² arg max VTT (s) #ell
where II consists of all deterministic non-anticipating Markov policies. Similarly, we define the corresponding Q functions to be
@ī(s,a) = (s, a)+ Σ S'ES
and = a)+ Σ (s
Human-centric system. The theme of the formulation and all our following results is a human- centric decision system where the machine acknowledges the suboptimal behavior the human and makes advice critical states improve the reward. So the learning and optimization of our paper take the perspective of the machine (solving An and do not seek to change the underlying human policy "
3

---

Published as a conference paper at ICLR 2024
3 THE LEARNING PROBLEM
Now we discuss learning problems associated with the above human human-maching adherence model. We consider two learning environments for the problem:
ε (Environment 1 -partially known): the environment's state transition kernel p, the reward r; and the human's behavior policy n², are known; the human's adherence level 0 is unknown.
& (Environment 2 fully unknown): the environment's state transition kernel p. the reward r, the human's behavior policy n², and the human's 's adherence level 0 are unknown.
For Ei, the goal is simply to learn the optimal policy under the unknown adherence level O. We develop a learning algorithm that outputs e-optimal advice policy and features better sample complexity compared to the vanilla application of problem-agnostic RL methods on .MM.. For Eg, we know neither the environment nor the human's 's policy. Thus the learning problem entails learning the dynamics of both the environment and the human policy. We develop a provably convergent learning algorithm that outputs the optimal policy, and in addition, the learned advice policy only gives advice when necessary (choosing to defer for non-critical steps).
Our investigations on these two learning formulations highlight three points. First, the inherent structure of the human-machine interaction allows more sample-efficient algorithms (than the vanilla application of the off-the-shelf RL algorithms) both theoretically and empirically. Second, the knowledge of the underlying environment (E1 compared against Eg) significantly, also unsurprisingly, reduces the sample complexity of the learning algorithm. Third, we establish a close connection be- interaction with the problems of reward-free exploration
tween the formulation of the (Jin et al. 2020) and constrained MDPs (Altman 20211.
3.1
MAIN RESULTS
We first state the technical results and then present the detailed algorithms and analyses in the subsequent section.
Theorem 1 (Environment& E informal) For environment ε,, Algorithm finds an c-optimal advice policy with PAC sample complexity (( with high probability.
Under environment E.. Theorem 1 gives PAC sample complexity for the UCB-type (Upper-
Confidence- Confidence-Bound-yyee) Algorithm T We remark that applying the existing problem-agnostic algorithms can only achieve a suboptimal order of sample complexity on the problem: 53 via the model-basees algorithm (Dann and Brunskill 2015) and O(H*SA/e via the model-free Specifically, the bound in Dann and Brunskill 2015) gives additional
algorithm JJin et al. 2018 [1 factor of H compared to the bounds in the original setting, where stationary transition density is assumed; this due to the fact that though the adherence level is stationary, the transition becomes non-stationary when compounding 0 and underlying transition of the human's 's underlying MDP. Also, we note that such an improvement on H/ is not due reduction in the number of unknown parameters because the adherence level 0 has dimensionality of SA. Indeed, the key to the improvement is the intrinsic structure of the human- suman-machine problem enables more sample-efficient design of the UCB algorithm (See Section 4.1 for details). Moreover, we also provide another algorithm that finds an e-optimal advice policy with sample complexity of O(H3SA/ for E2 (See Algorithm 3 in appendix A.3 for details).
For environment Eg, we assume no prior knowledge at all, and this makes the machine's problem no different than generic RL problem. Thus we consider slight twist of the machine's MDP with the notion of pertinent advice. This twisted formulation enables richer analytical structures and draws interesting connections with several existing frameworks. Specifically, consider
machine's 's
MDP M E (S. H. H. which inherits everything from A (S. H pM, rM) except for the reward
N = ( - 3 I[a defer}.
'The authors obtain regret bound instead of PAC sample complexity bound. However, they convert the regret bound to PAC sample complexity hound in (Tin al. 2018 Section 3.1)
4

---

Published as a conference paper at ICLR 2024
where the }{-} is the indicator function and 3 0 is constant. Under M denote V and V3 the value functions of and the optimal value function, respectively, and the optimal policy Ty E arg m V The new reward function enforces a penalization of ( for making advice and thus regularizes the number of machine advices throughout the horizon. In practice, providing advice to human at every step can be annoying in applications such as gaming, driving, or sports. Hence, it is crucial to prioritize and selectively deliver advice based on its criticalness which we term informally as perlinent advice. For example, when the human is an expert and already achieves near-optimal and the
performance, there is no need to give advice; also, when the human is under-performen adherence level is low, there is also no need to give advice because it is unlikely to be taken.
Proposition 1. For all E S and h [H] such that Th (s) defer, have
(s, 2h (s)) V (s) 2 B.
The proposition says that if the machine takes (s) and sticks with the optimal policy afterward, the reward will be at least 3 more than that if the machine chooses to defer all the way till the end. In this light, we can rank the criticalness of making advice different states by solving M with different B which gives better interpretation of this human-machine system.
Theorem 2 (Environment Eg, informal) For Eg, Algorithm 2 { for [M3)s> with O(HSSA/e) episodes such that the following inequality
outputs family of c-optimal policies
(11) (s1) Se
1,8 (s1)
(4)
holds uniformly for all 3 >> 0 with high probability.
Theorem 2 gives the sample complexity of Algorithm which learns a near-optimal policy for all the models [MM)s2) simultaneously. Such joint learming not only provides a family of policies for the human to customize 3 according to her/his performance but also gives us handle to understand which are the critical states where the human's policy can be significantly improved.
4 ALGORIHTMMS AND ANALYSES
In this section, we present the algorithms and analyses that achieve the results mentioned previously.
4.1 UCB-BASED ALGORITHM FOR &
Under ε₁, the machine works with a human with unknown adherence level 0. An important property of A as follows. Basically, states that the team of human and machine achieves a higher optimal reward if the human has a higher adherence level. To emphasize the dependence on 6, we write
Vi (s|0) E Σ (sW. sn s, adherence parameter 0 and V (s(0)
max V (s|0). well
(Monotonicity property). Suppose 01 2 02 holds entry-wise, then the following inequality holds for all E S and h [H]
Proposition
(s(()))) 2 (s(02).
Proposition 2 implies that finding an upper bound for the optimal value function reduces to finding an upper bound for 0. Algorithml] follows this implication and maintains an optimistic estimate 0 for the true parameter 0. For each episode, it generates the policy म pretending the 0* as true, and rolls out the episode according to म. Then it updates the estimate with the new observations. The optimistic estimate 0¹ takes the form of standard UCB form with careful choice of the confidence width and we defer more details to Appendix A.2 The algorithm shares the same intuition as other UCB-based algorithms that, with more and more observations, the confidence bound 0' will shrink to the true 0, and so does the value functions.
Theorem establishes (e, PPCC result for Algorithm 1
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 UCB-ADherence (UCB-AD)
1: Input: Target probability level 8.
2: Initialize / = 1, D - 0, and the optimistic estimate 0' 1.
3: for (= 1, ... do
4: Solve the advice policy #' = arg max, (-10') given the current optimistic estimate 0'
5: Sample a new episode 2 = {s 01 di .i." S " "H rf following policy at
6: Update D, < D U {z+}
7: Update the optimistic estimate 0' - 0++1 based on Dr and 8
8: end for
Theorem 1. For any 8 E (0, E (0, 1), and T E N+, the number of policies among (#*]T= Algorithm that are not e-optimal, i.e. Vi(81) - Vf* (s1) > is bounded by Ô 112 52 log }
=t= from
with probability 1 d- 6.
The proof of the theorem mimics the analysis of Dann and Brunskill (2015). One caveat in the analysis is that the original analysis Dann and Brunskill (2015) focuses on stationary setting where transition probabilities depend solely on state and action, remaining independent of the time horizon. However, even when the adherence level 0 remains the same over time, the machine's 's MDP is non-stationary. An direct adoption is to enlarge the state space to incorporate the horizon step h, yet this will result sample complexity of 3 5² A/c²), worse dependency on H. The key is to reduce the upper bound analysis to the adherence level space and utilize Proposition 2o convert that into a suboptimality gap with respect to the value function. This treatment gives the desirable which also outperforms the bound from direct application of results from Azar et al. 2017) to non-stationary MDPs.
bound in Theorem |
4.2 REWARD-FREE EXPLORATIONN ALGORITHM FOR &
Eg has more unknown parameters than E and thus it naturally entails more intense exploration. Moreover, the learning objective becomes more complex: we aim not only to learn the near-optimal policy but also discern the pertinent advice.
Algorithm?2 is based on the concept of reward-free exploration (RFE) (Jin et al. 2020). Specifically, RFE algorithms usually consist of an exploration phase and planning phase. During the exploration phase, the algorithm collects trajectories from an MDP . without pre-specified reward function. In the planning phase, it can compute near-optimal policies of M, given any deterministic reward functions that are bounded.
In our human-machine machine model, the machine observes Sh. - a a Sh+1, and the trajectory for H.t. episode L is 2 {o4, ait ai ,ri, 56 dg az
n.t. H.t
rrg, , , az , r r. where d; n, n² (s()). M.t
N,t H.3.
an (-1s% 4% M.t). and sh ~ ph (-15h ax ). We denote Ph and AM.t the empirical estimation for p" and rxx, and n (s, a) = Ei= If s) ah M.i)
(s, (s,aa) a)} the number of times the machine gives advice at time h and state in the first episodes. The key quantity in Algorithm 2 is
(x, = min H, 16 (n) a),
+ (1 (1+ + })
Σ Ph (8'18, max ( .d)
n/, ())
a'
(5)
where W WHr41(s.5 (s) = 0 for (s. E S x A, and Φ(n,8) grows at the order of O(log(n) + log(1/5))
and is specified in Theorem
Now we formally introduce our Algorithm 2 The algorithm iteratively minimizes an upper bound defined by (5) which measures the uncertainty of 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. This algorithm is inspired by the RF-Express algorithm (Ménard et al. 2021), and there is slight difference in the definition of W (s, a). o(n, 8) and the stopping rule. In our application. the reward nM is stochastic and we need to take care of the estimation error; while in Ménard al. (02T), the algorithm does not need deal with the reward at all.

---

Published as a conference paper at ICLR 2024
Algorithm 2:
RFE-3
1: Input: 6, and user-spedified (3. where I could be any set where 3r E [0, H)
2: Stage 1: Reward-free exploration
3: Initialize 1. and W7,ss,
H for all (8,a) E S x A
4: Compute x' so that (8) = arg max [8 a) (see (5)
5: while Wf(SI, (s1)) + /e/Wi ( (>())) e/H do
6: Sample trajectory 2; {st, 01 44
.f. , SH,aH aH . ri following o' Mit
H.t. B.t
7: update / - L + 1, D + DU { (611, l (8, and (s,
8: end while
9: Stage 2: Policy identification
Use planning algorithms to output optimal advice policy (#7, hie for (S,A.
Theorem 2. For 8 (0,1), (0, and Φ(n, 8) 6 6log(4H(SA/(cd)) + log(8e(n + 1)), with probability - 6, Stage I of Algorithm stops in episodes and
SA
$ C1
22 (6log(4HSA/(<e))) S),
where C1 = (((lo((HSA)) Moreover, ( have the following property
P ((Vi,((5)) Vi, (s1) S uniformly for all 3 [0. 11
Theorem ensures that Algorithm 2 provides sample estimation for the underlying MDP such that all the policy { (0 for pertinent advice are near optimal. The proof is a direct application of the RF-Express (Ménard et al. 2021), except that we have take
of the estimation error in fa. Although Algorithm 2 has the uniform convergence property for any number of bounded reward functions, can also be used the same way as Algorithm | find the e-optimal policy for M if provided with the non-penalized reward function fM. In this context, we can modify RFE-3 so that with high probability, it solves M with sample complexity of O(H)SA)e) (See Algorithm in Appendix A.3 for details).
CMDP for pertinent advice. The algorithm RFE-3 solves class of problems Jes0 simultane- ously for all the I's and measures the pertinence of advice by 3. However, sometimes humans lack a quantitative view of how large a 3 value should be considered as pertinent. Here, we introduce different perspective
how the human should rank the importance of advice, framing "in H steps, I want advice no more than D times", and formulate this CMDP problem
E" Σ (sh,, an))
s.l. E. Σ Man + defer)
D,
(6)
where E (0, H). From the standard primal-dual theorem, this formulation is closely related to the treat dual variable for the constraint D. We refer the reader to the proof of Corollary iin Appendix A.3 for details.
penalty / in (3), for the reason that
Now present the CMDP method for pertinent advice. After stage 1 of RFE-3, solve
H
H
max
M.T (sh, an))
s.t.
Σ
Ian + defer}
< D
where Ê is the expectation with the underlying transition being GM. The next corollary states that th. the solution for 7 is near-optimal policy for the CMDP (6)
Corollary 1. In the same setting of Theorem 2 for 8 (0,1) 1) and e E (0. 1), with probability 1 - 8, for all D E (0, H), #T is a near-optimal solution for the original CMDP (6) such that
B
v 2c,
and
Σ
T(a # defer)
< D +
(8)
where γ. DD is the optimal solution for T

---

Published as a conference paper at ICLR 2024
Corollary 1 also implies that RFE-3 can compute near-optimal policies of CMDP (6) for all the constraints D E [0, H), with a sample complexity of O(H' SA/c*). Compared to other CMDP learning algorithms (for example, O S A/c²) ) in Kalagarla al. (202))) the sample complexity of Corollary features a lower order in S. Moreover, the near-optimal result holds for all constraints D E [0, H), and for other CMDP learning algorithms, the result only holds for pre-specified D.
5 NUMERICAL EXPERIMENT
We perform numerical experiments under two environments: Flappy Bird (Williams et al. 20233 and Car Driving Meresht et al. (2020). Both Atari game-like environments are suitable and convenient for modeling human behavior while retaining the learning structure for the machine. We focus on the flappy bird environment here and defer the car driving environment to Appendix
Flappy Bird Environment. We consider game map of 7-by-20 grid of cells. Each cell can be empty, contain star, or act as a wall. The goal to navigate the bird across the map from left to right and collect as many stars as possible. However, colliding with wall reaching the (upper and lower) boundaries leads to the end of the game. An example map is displayed in Figure [I, which splits into three phases: the first phase contains almost only stars and walls, the second phase contains almost only walls and very few stars, and the third phase contains both stars and walls.
First Phase
Second Phase
Third Phase
Figure 1: Flappy Bird environment: player needs navigate the bird to avoid walls and collect stars.
We define the state space as the current locations the bird on the grid, represented by coordinates y)) E ZZ, with a total of 7 x 20 = 140 states. Regarding the action space, we define it as A= (Up. Up-Up, Down]. Each action causes the bird to move forward by one cell. addition, the "Up" action moves the bird one cell upwards, the "Up-Up" action moves it two cells upwards, and the "Down" action moves it one cell downwards. The MDP has reward as a function of state only. We will get reward of 1 when the current state (location) has star and otherwise 0. To model human behavior, we consider two sub-optimal human policies: Policy Greedy, which prioritizes collecting column, and Policy Safe, which focuses avoiding walls in the next column. If
stars in the there is no preferred action available, both policies maintain a horizontal zig-zag line by alternating between "Up" and "Down".. For adherence level 0, we assume for all s S and h ..., H, the human will adhere to the advice with probability 0.9 except the aggressive advice "Up-up" (which moves too fast vertically) with adherence level 0.7. We compare the following algorithms:
UCB-ADherence (UCB-AD): Algorithm that finds the e-optimal advice policy.
RFE-ADvice (RFE-AD): Algorithm 3 variant of RFE-3 that finds the e-optimal policy.
RFE-3: Algorithm 2 that outputs pertinent advice policy by exploring then planning.
RFF-CMDP: A variant of RFE-3 that solves the CMDP after exploring.
Figure 2a and 26 present the results for the two algorithms UCB-AD and RFE-AD for the environment
& also includes the ofate-of-the-art algorithm EULER Zanette and Brunskill] 2019) that achieves generic minimax optimal regret. From the regret plot, UCB-AD outperforms both RFE-AD and EULER. This advantage attributed to UCB-AD's effective utilization of the information and structure of the underlying MDP. These results also show that tailored algorithms UCB-AD and RFE-AD are much more efficient than directly applying problem-agnostic RL algorithms in the adherence model. We further test UCB-AD with different 6's: with 0, 0(a, s) 0.8 and with 82 f(a, s) = 0.4. Figure 20 shows the relationship between the regret UCB-AD and 6: for both policies, UCB-AD can achieve smaller regret with higher O. Intuitively, high adherence level implies
8

---

Published as a conference paper at ICLR 2024
high probability of following the advice instead of taking x², which will reduce the regret caused by the suboptimality of n".
=10º
x10*
X102
RFE-AD
RFE-AD
UCD
UCD AD
EULER
Degret
Reggett
Sale, Grendy, Greedy. R
8
10
15
20
500
1000
1500
Episade
K10
Episade
x10
Episode
(a) Regrets of Policy Greedy.
(b) Regrets of Policy Safe.
(c) Regrets of UCB-AD.
Figure 2: The regrets for learning the optimal advice for Policy Greedy and Policy Safe. Figure
2b show the regrets of RFE-AD, UCB-AD, and EULER for two policies respectively, Figure 2c shows the regrets of UCB-AD for two policies under different 0's.
Figure 3 summarizes results for three policies under the environment &g. namely RFE-8, RFE- CMDP, and UC-CFH, a provably convergent CMDP algorithm (Kalagarla et al. (021), under Policy Safe. Figure 3a we see that RFE-3 exhibits convergence for different B's, and this empirically corroborates the theoretical finding. In Figure 3b we compare RFE-CMDP and UC-CFH under simpler environment with the advice budget being (D = 1). We observe that marginal performance advantage over UC-CFH in terms of the convergence rate. More importantly, Belshoss by only using the estimated transition kernel after learning for RFE-CMDP is able to obtain near-optimal policy for problem instances with different advice budgets (D 2, and 5). However, UC-CFH fails explore the whole transition kernel sufficiently and only output the near-optimal policy for the original problem instance. Moreover, RFE-CMDP more sample efficient with respect to the advice budget, because for UC-CFH, we have to run multiple times with different advice budget parameters to get near-optimal policy for all of them.
shows
(Figure (b)),
0=
0=0
1.00
UC-CFH
RFE-CMDP
0.8
RFE-CMDP UC-CFH
Value Gap
0-4
Value Gap
0.75
Value Gap
0.6
0.4
1-
0.25
0.2
0.00
0.0
0.0
0.5
1.0 Episode
1.5
2.0
0.0
0.5
1.0
1.5
1
2
3
x10
Episode
x10
Budget
(a) Value gaps of RFE-8.
(b) Value gaps w.r.t episode.
(c) Value gaps when evaluating.
Figure 3: The performances of making pertinent advice. The value gap is defined the difference between the value of current policy and the optimal values, with the red dashed line as the benchmark for 0 loss of the policy. Figure 3a shows the convergence of RFE-3 under difference f3'. Figure 3b compares the convergences RFE-CMDP and UC-CFH. Figure 3d evaluates performance policy learned from learning episodes in Figure 3b
Lastly, show that 3 is capable of generating pertinent advice for different policies. Figure displays representative trajectories of two policies playing the game while receiving guidance from the machine, which follows itg trained in the experiment of Figure 2 By setting 3 0.3, the machine outputs a policy that only gives advice when necessary: Since Policy Greedy behaves well in the first phase, the machine almost only gives advice in the second phase and the third phase; Similarly, the machine almost only gives advice in the first phase and the third phase, and choose to defer most of the time when Policy Safe is in the second phase.

---

Published as a conference paper at ICLR 2024
First Phase
Second Phase
Third Phase
First Phase
Second Phase
Third Phase
(a) Trajectory Policy Greedy.
Trajectory of Policy Safe.
Figure 4: Typical trajectories of two policies' types. The red color means the machine defers and the green color means the machine advises.
REFERENCES
Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR,
2017.
Avinash Balachandran, Tiffany L Chen, Jonathan YM Goh, Stephen McGill, Guy Rosman, Simon Stent, and John Leonard. Human-centric intelligent driving: Collaborating with the driver improve safety. In Automated Road Transportation Symposium, pages 85-109. Springer, 2021.
Hamsa Bastani, Osbert Bastani, and Wichinpong Park Sinchaisri. Improving human decision-making with machine learning. arXiv preprint arXiv:2108. 08454, 2021.
Andreea Bobu, Dexter RR Scobee, Jaime Fisac, S Shankar Sastry, and Anca Dragan. Less is more: Rethinking probabilistic models of human behavior. In Proceedings of the 2020 acm/ieee international conference on human-robot interaction, pages 429-437, 2020.
Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. Advances in neural information processing systems, 32, 2019.
Min Chen, Stefanos Nikolaidis, Harold Soh, David Hsu, and Siddhartha Srinivasa. Planning with trust for human-robot collaboration. In Proceedings of the 2018 ACM/IEEE international conference on numaan-rboot interaction, pages 307-315, 315, 2018
Ningyuan Chen, Ming Hu, and Wenhao Li. Algorithmic decision-making safeguarded by human knowledge. arXiv preprint arXiv:2211.11022 2022.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Advances in Neural Information Processing Systems, 28, 2015.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez Rodriguez. Classification under human assistance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Julien Grand-Clément and Jean Pauphilet. The best decisions are not the best advice: Making adherence-aware recommendations. arXiv preprint arXiv:2209.0187. 2022.
Joey Hong, Anca Dragan, and Sergey Levine. Learning to influence human behavior with offline reinforcement learning. arXiv preprint arXiv:2303.02265 2023.
10

---

Published as a conference paper at ICLR 2024
Alexis Jacq. Johan Ferret, Olivier Pietquin, and Matthieu Geist. Lazy-mdps: Towards interpretable reinforcement learning by learning when to act. arXiv preprint arXiv:2203.08542. 2022.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879. PMLR, 2020.
Krishna C Kalagarla, Rahul Jain, and Pierluigi Nuzzo. A sample-efficient algorithm for episodic finite- horizon mdp with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8030-8037, 2021.
Emilic Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891. PMLR, 2021.
Zahra Rezaei Khavas, S Reza Ahmadzadeh, and Paul Robinette. Modeling trust in human-robot interaction: A survey. In International conference on social robotics, pages 529-541. Springer, 2020.
Cassidy Laidlaw and Anca Dragan. The boltzmann policy distribution: Accounting for systematic suboptimality in human models. arXiv preprint arXiv:2204.100 10759, 2022.
Tor Lattimore and Marcus Hutter. Near-optimal pac bounds for discounted mdps. Theoretical Computer Science, 558: 125-112-111 143, 2014.
Anqi Mao, Christopher Mohri, Mehryar Mohri, and Yutao Zhong. Two-stage learning to defer with multiple experts. Advances in neural information processing systems, 36, 2023.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration reinforcement learning. In Interna- tional Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
Vahid Balazadeh Meresht, Abir De, Adish Singla, and Manuel Gomez Rodriguez. Learning to switch between machines and humans. arXiv preprint arXiv:2002.04258, 2020.
Gomez-Rodrigeee
Sobhan Miryoosefi and Chi Jin. A simple reward-free approach to constrained reinforcement learning. In International Conference on Machine Learning, pages 15666-15698. PMLR, 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 5 518(7540):529-537 2015.
Christopher Mohri, Daniel Andor, Eunsol Choi, and Michael Collins.
Learning reject with fixed predictor: Application to decontextualizatton. arXiv preprint arXiv:2301.09044, 2023.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In International Conference Machine Learning, pages 7076-7087. PMLR, 2020.
Nastaran Okati, Abir De, and Manuel Rodriguez. Differentiable learning under triage, Advances in Neural Information Processing Systems, 11191099955, 2021.
Mohammed Yousef Shaheen. Applications of artificial intelligence (ai) in healthcare: A review. ScienceOpen Preprints, 2021.
Lior Shani, Yonathan Efroni, and Shie Mannor. Exploration conscious reinforcement learning revisited. In International conference machine learning, pages 5680-5689. PMLR, 2019.

---

Published as a conference paper at ICLR 2024
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)335-3355 2017.
Eleni Straitouri, Adish Singla, Vahid Balazadeh Meresht, and Manuel Gomez-Rodriguez. Reinforce- ment learning under algorithmic triage. arXiv preprint arXiv:2109. 1328, 2021.
Jiankun Sun, Dennis Zhang, Haoyuan Hu, and Jan A Van Mieghem. Predicting human discre- tion to adjust algorithmic prescription: large-scale field experiment warehouse operations. Management Science, 68(2):846-665, 2022.
Katherine Williams, Madeleine Yuh, and Neera Jain. A computational model of coupled human trust and self-confidence dynamics. ACM Transactions on Human-Robo Interaction, 2023.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:11734 1743, 2020.
12


Reviews:
[{"review_id": "fSqPE90Sk5", "reviewer": "Reviewer_7r6M", "summary": "This paper formalizes the setting of a static policy taking advice from another policy as an MDP. The authors use this abstraction to study the setting of a human taking advice from a machine in order to perform better on a decision-making task. Crucially, this MDP assumes the human (i.e. the static policy that receives machine advice) only follows the advice (i.e. a recommended action) with a probability $\\theta$ per state. The paper then 1. introduces UCB-based algorithms to solve the case where the environment dynamics and human policy are know, but $\\theta$ is unknown, and 2. adapts reward-free exploration methods to solve the case where the dynamics and advice-taking policy are additionally unknown, whereby the MDP is modeled as a CMDP. The experiments focus on a toy environment based on Flappy Bird and two toy, hard-coded policies (\"Greedy\" and \"Fixed\"). In this latter setting, the authors show their reward-free expoloration method, RFE-$\\beta$ can successfully provide advice to improve the performance of the two fixed policies.", "questions": "- Does this method handle higher-dimensional environments or continuous action spaces?\n- How does this method handle more complex adherence functions?\n- How does this method handle co-adapting advice takers?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper deals with the important topic of human-AI collaboration, a topic that is largely overlooked by the greater ML community in favor of fully-autonomous approaches. In particular, advice-taking is an important setting of human-AI collaboration, and the formalization of this setting as a CMDP, while straightforward, presents an important step toward making progress on this important problem. \n- Overall, the presentation is highly legible and the key ideas are explain clearly.", "weaknesses": "While this paper studies an important topic, the paper should be improved before acceptance to a top-tier conference like ICLR:\n- The experimental setting is extremely simplistic. The Flappy Bird MDP effectively consists of just 2 actions (up or down). The exact layout of MDP also appears fixed. Likewise, the advice-taking policies are fixed as two hard-coded policies. Effectively, the problem then reduces to learning a policy to solve 2 static MDPs with very small action spaces. Ideally the study can look at Flappy Bird under a procedurally-generated setting as well as look at other environments with higher-dimensional observation and action spaces.\n- It would also be ideal to include an environment with continuous action spaces.\n- The experimental setting also buckets all states into 2 coarse groupings of adherence levels for the advice-taking policy. In practice, the adherence levels are likely more complex and also time-varying. It would improve the paper to include experiments with a co-adapting advice-taking policy.\n- In extending this work to higher-dimensional environments, the authors should consider comparing their approaches to existing deep RL methods for exploration [1,2] as baselines.\n\n**Minor comments**\n- In the related works section, the authors should include citations to the line of works studying human-AI cooperation in Hanabi: \n    - Bard, Nolan, et al. \"The hanabi challenge: A new frontier for ai research.\" Artificial Intelligence 280 (2020): 103216.\n    - Foerster, Jakob, et al. \"Bayesian action decoder for deep multi-agent reinforcement learning.\" International Conference on Machine Learning. PMLR, 2019.\n    - Hu, Hengyuan, et al. \"Off-belief learning.\" International Conference on Machine Learning. PMLR, 2021.\n\n\n**References**\n\n[1] Ciosek, Kamil, et al. \"Better exploration with optimistic actor critic.\" Advances in Neural Information Processing Systems 32 (2019).\n[2] Osband, Ian, et al. \"Deep Exploration via Randomized Value Functions.\" J. Mach. Learn. Res. 20.124 (2019): 1-62.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "F4G7wbY9On", "reviewer": "Reviewer_X7E8", "summary": "This paper studies a reinforcement learning model that takes into account the human’s adherence level and incorporates a defer option so that the machine can temporarily refrain from making advice. The authors provide novel algorithms based on the principle of optimism in the face of uncertainty, which can learn the optimal advice policy and make advice only at critical time stamps. The authors further present the theoretical guarantee of the proposed algorithms and show their empirical performance.", "questions": "Please see the sections above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work investigates a novel reinforcement learning model taking into account new realistic factors, including the human 's adherence level and the defer option. The corresponding algorithm design and the theoretical analysis are novel to reinforcement learning. The empirical studies also verify the algorithms' performance. In addition, the paper is well-structured, and the main idea of this work is easy to follow.", "weaknesses": "(1) The major concern about this work is that there is a gap between the result for $\\mathcal{E}_1$ in Algorithm 1 and that for $\\mathcal{E}_2$ in Algorithm 3. The dependence on $S$ is typically more important than $H$ in the reinforcement learning problem. As claimed by the authors, the sample complexity bound for Algorithm 3 is sharper in the dependence on S than for Algorithm 1. But $\\mathcal{E}_2$ should be a harder problem than $\\mathcal{E}_1$, and thus the sample complexity bound for $\\mathcal{E}_1$ is expected to be better. Can the authors discuss why there is such a gap and whether it is possible to modify Algorithm 1 to have a better sample complexity bound matching the one for Algorithm 3 in terms of $S$?\n\n(2) Can the authors point out which part of the supplement is for the theorem and the corresponding proof of Algorithm 3? It appears not explicitly presented in the paper, although the authors have shown its sample complexity result in the main text.\n\n(3) Eq.(1) is not clearly explained, especially the third case in Eq.(1). Can the authors provide some more explanation on how the probability of the third case is obtained?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "mSQ8jUgupb", "reviewer": "Reviewer_tRbR", "summary": "This paper studies the problem of learning to give advice to humans assuming humans may take the advice or not according to some underlying adherence level. The paper presents a formal problem definition of the problem, two UCB-style algorithms, and a theoretical analysis with convergence bounds.", "questions": "I don't have any specific questions. \n\nI think this paper should be ultimately evaluated according to the strength of its theoretical results, which is out of my expertise. My current rating is based on its presentation but I'm okay to raise the score if other reviewers would champion its theoretical contributions.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. **Problem formulation:** This paper proposes a new formulation of advising by assuming a fixed human player with a fixed probability of taking advice. This problem formulation to me is novel by considering the human adherence level. \n\n2. **Theoretical analysis:** The paper adopts a few theoretical analysis frameworks to this advising problem and derives much-improved convergence bounds by leveraging the problem structures. \n\n3. **Empirical studies:** It is nice to see the algorithm really works on the flabby bird domain although it is simple.", "weaknesses": "My biggest complaint about this paper is its presentation. A few comments are listed below.\n\n1. It is weird that there is no citation at all in the introduction section. The introduction part is also particularly short with the contribution statements even deferred after the related work section. I would strongly encourage the authors to expand the introduction with more detailed explanations and more intuitions. \n\n2. I think the \"**Theoretical reinforcement learning**\" section should be expanded a bit, e.g., to be an independent background section. I think this part is the most relevant literature. It would be better if the paper could spend more texts explaining the connection and differences between the existing literature and the current work from a more technical perspective. \n\n3. It is strange to me that the convergence bounds are introduced even before the algorithms. This makes it difficult for the readers to follow the insights.\n\n4. It is so tough for me to fully follow section 4.2. Equation (5) looks like a magical number to me and I have no idea how it is derived and why such a structure helps improve the bound from reward-free learning. I'm not a theoretical person. Carefully checking every detail of the proof is out of my capacity, so it would be great for me if the paper could explain well the insights of why the structure helps improve the bound for an outsider. \n\n5. It is stated in the experiment section that two testbeds are considered, including the Flabby Bird domain and the Car Driving domain. However, I cannot find the Car Driving results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": {}}]

Author rebuttal:

Decision: Accept (poster)