Learning to Switch Among Agents in a Team via 2-Layer Markov Decision Processes
Authors: Vahid Balazadeh
Abir De
Adish Singla
Manuel Gomez Rodriguez
Venue: Accepted by TMLR ()

Abstract: Reinforcement learning agents have been mostly developed and evaluated under the assumption that they will 
operate in a fully autonomous manner---they will take all actions. In this work, our goal is to develop algorithms that, by learning to switch control between agents, allow existing reinforcement learning agents to operate under different automation levels. To this end, we first formally define the problem of learning to switch control among agents in a team via a 2-layer Markov decision 
process. Then, we develop an online learning algorithm that uses upper confidence bounds on the agents' policies and the environment's 
transition probabilities to find a sequence of switching policies. The total regret of our algorithm with respect to the optimal switching policy is sublinear in the number of learning steps and, whenever
multiple teams of agents operate in a similar environment, our algorithm greatly benefits from maintaining shared confidence bounds for the 
environments' transition probabilities and it enjoys a better regret bound than problem-agnostic algorithms. Simulation experiments in an obstacle avoidance task illustrate our theoretical findings and demonstrate that, by exploiting the 
specific structure of the problem, our proposed algorithm is superior to problem-agnostic algorithms.

Published in Transations on Machine Learning Research (07/202)
Learning to Switch Among Agents in a Team via 2-Layer Markov Decision Processes
Vahid Balazadeh University of Toronto
vahid@cs.toronto
Abir De
abir@cse.
Indian Institute of Technology Bombay
Adish Singla
adishs @mppisss.doo.ooo
Maz Planck Institute for Software Systems
Manuel Gomez Rodriguez
manuelgr@mpi.eus..gg
Mas. Planck Institute for Software Systems
Reviewed on OpenReview:
Abstract
Reinforcement learning agents have been mostly developed and evaluated under the assump- tion that they will operate in fully autonomous manner-ther will take all actions. In this work, our goal is to develop algorithms that, by learning to switch control between agents, allow existing reinforcement learning agents to operate under different automation levels. To this end, we first formally define the problem of learning to switch control among agents in a team via a 2-layer Markov decision process. Then, we develop an online learning algorithm that uses upper confidence bounds on the agents' policies and the environment's transition probabilities to find sequence of switching policies. The total regret of our algorithm with respect to the optimal switching policy is sublinear in the number of learning steps and, when- ever multiple teams of agents operate in similar environment, our algorithm greatly benefits from maintaining shared confidence bounds for the enviromments' transition probabilities and enjoys a better regret. bound than problem-agnostic algorithms. Simulation experiments illustrate our theoretical findings and demonstrate that, by exploiting the specific structure of the problem, our proposed algorithm is superior problem-agnostic algorithms.
1 Introduction
In recent years, reinforcement learning (RL) agents have achieved, even surpassed, human performance in variety of computer games by taking decisions autonomously, without human intervention (Mnih et al., 2015; Silver et al., 2016; 2017; Vinyals et al., 2019). Motivated by these successful stories, there has been a tremendous excitement on the possibility of using RL agents to operate fully autonomous cyberphysical systems, especially in the context. of autonomous driving. Unfortunately, number of technical, societal, and legal challenges have precluded this possibility become so far reality.
In this work, argue that existing RL agents may still enhance the operation of cyberphysical systems if deployed under lower automation levels. For example, if we let RL agents take some of the actions and leave the remaining oncs to human agents, the resulting performance may be better than the performance either of them would achieve on their own (Raghu et al., 2019a; De el al., 2020; Wilder el al., 2020). Once we depart from full automation, we need to address the following question: when should we switch control between machine and human agents? In this work, we look into this problem from thcoretical perspective and develop an online algorithm that learns optimally switch control between multiple agents in a team automatically. However, fulfill this goal, we need to address several challenges:

---

Published in Transations on Machine Learning Research (07/202)
Level of outomation. In each application, what is considered an appropriate and tolerable load for each agent may differ (European Parliament, 2006). Therefore, we would like that our algorithms provide mechanisms to adjust the amount of control for each agent (de., level of automation) during a given time period.
Number of switches. Consider two different switching patterns resulting in the same amount of agent control and equivalent performance. Then, we would like our algorithms to favor the pattern with the least number of switches. For example, in a team consisting of human and machine agents, every time a machine defers (takes) control to (from) human, there is an additional cognitive load for the human (Brookhuis et al., 2001).
Unknown agent policies. The spectrum of human abilities spans a broad range (Macadam, 2003). As a result, there is a wide variely of potential human policies. Here, we would like that our algorithms learn personalized switching policies that, over time, adapt to the particular humans (and machines) they are dcaling with.
Disenlangling agents' policies and environment dynamics. We would like that our algorithms learn to disentangle the influence of the agents' policies and the environment dynamics on the switching policies. By doing so, they could be used to efficiently find multiple personalized switching policies for different teams of agents operating in similar environments (e.g., multiple semi- anni-autonooous vehicles with different human drivers).
To tackle the above challenges, we first formally define the problem of learning to switch control among agents in a team using a 2-layer Markov decision process (Figure 1). Here, the team can be composed of any number of machines human agents, and the agents' policies, as well as the transition probabilities of the enviromment, may be unknown. In our formulation, we assume that all agents follow Markovian policies", similarly as other theoretical models of human decision making (Townsend et al., 2000; Daw & Dayan, 2014; McGhan et al., 2015). Under this definition, the problem reduces to finding the switching policy that provides an optimal trade off between the environmental cost, the amount of agent control, and the number of switches. Then, we develop an online learning algorithm, which we refer to as UCRL22MM that uses upper confidence bounds on the agents' policies and the transition probabilities of the environment to find sequence of switching policies whose total regret with respect to the optimal switching policy is sublinear in the number of learning steps. In addition, we also demonstrate that the same algorithm can be used to find multiple sequences of switching policies across several independent teams of agents operating in similar environments, where it greatly benefits from maintaining shared confidence bounds for the transition probabilities of the environments and enjoys a better regret bound than UCRL2, a very well known reinforcement learning algorithm that we view as the most natural competitor. Finally, we perform a variety of simulation experiments in the standard RiverSwim environment as well as an obstacle avoidance task, where we consider multiple teams of agents (drivers) composed by one human and one machine agent. Our results illustrate our theoretical findings and demonstrate that, by exploiting the specific structure of the problem, our proposed algorithm is superior to problem-agnostic alternatives.
Before we proceed further, we would like to point out that, at a broader level, our methodology and theoretical results are applicable to the problem of switching control between agents following Markovian policies. As long as the agent policies are Markovian, our results do not distinguish between machine and human agents. In this context, we view teams of human and machine agents as one potential application of our work, which use a motivating example throughout the paper. However, we would also like to acknowledge that a practical deployment of our methodology in a real application with human and machine agents would require considering a wide range of additional practical aspects (e.g., transparency, explainability, and visualization). Morcover, one may also need to explicitly model the difference in reaction times between human and machine agents. Finally, there may be scenarios in which it might be beneficial to allow a human operator to switch control. Such considerations are out of the scope of our work.
In cortain cases, it possible convert non-Markovian human policy into a Markovian one by changing the state representa- tion (Daw & Dayan, 2014). Addressing the problem of learning to switch control among agents in team in semi-Markovian setting is left as a very interesting venue for future work. 2URR22 with Multiple Confidence sets.
2

---

Published in Transations on Machine Learning Research (07/2022)
2
Related work
One can think of applying existing RL algorithms (Jaksch et al., 2010; Osband et al., 2013; Osband & Van Roy, 2014; Gopalan & Mannor, 2015), such as UCRL2 or Rmax, to find switching policies. However, these problem-agnostic algorithms are unable to exploit the specific structure of our problem. More specifically, our algorithm computes the confidence intervals separately over the agents' policies and the transition probabilities of the environment, instead of computing a single confidence interval, as problem-agnostic algorithms do. As consequence, our algorithm learns to switch more efficiently across multiple teams of agents, as shown in Section 6.
There is a rapidly increasing line of work on learning to defer decisions in the machine learning litera- ture (Bartlett & Wegkamp, 2008; Cortes et al., 2016; Geifman et al., 2018; Ramaswamy et al., 2018; Geifman & El-Yaniv, 2019; Liu et al., 2019; Raghu et al., 2019a;b; Thulasidasan et al., 2019; De et al., 2020; 2021; Mozannar & Sontag, 2020; Wilder et al., 2020; Shekhar et al., 2021). However, previous work has typically focused on supervised learning. More specifically, it has developed classifiers that learn to defer by considering the defer action an additional label value, by training decisions, or by reducing the problem to combinatorial optimization problem. Moreover, except for few recent notable exceptions (Raghu et al., 2019a; De et al., 2020; 2021; Mozannar & Sontag, 2020; Wilder et al., 2020), they do not consider there is a human decision maker who takes a decision whenever the classifiers defer it. In contrast, we focus on reinforcement learning, and develop algorithms that learn to switch control between multiple agents, including human agents. Recently, Jacq ct al. (2022) introduced a new framework called lazy-MDPs to decide when act optimally for reinforcement learning agents. They propose to augment existing MDPs with new default action and encourage agents to defer recision-making to default policy in non-critical states. Though their lazy-MDP is similar to our augmented 2-layer MDP framework, our approach is designed to switch optimally between possibly multiple agents, each having its own policy.
independent classifier to decide about deferred
Our work is also connected to research on understanding switching behavior and switching costs in the context of human-computer interaction (Czerwinski et al., 2000; Horvitz & Apacible, 2003; Iqbal & Bailey, 2007; Kotowick & Shah, 2018; Janssen et al., 2019), which has been sometimes referred to as "adjustable autonomy" (Mostafa et al., 2019). At a technical level, our work advances state of the art in adjustable autonomy by introducing an algorithm with provable guarantees to efficiently find the optimal switching policy in setting in which the dynamics of the environment and the agents' policies are unknown (i.e., there is uncertainty about them). Moreover, our work also relates to a recent line of research that combines deep reinforcement learning with opponent modeling to robustly switch between multiple machine policies (Everett & Roberts, 2018; Zheng et al., 2018). However, this line of research does not consider the presence of human agents, and there are no theoretical guarantees on the performance of the proposed algorithms.
Furthermore, our work contributes to extensive body of work on human-machine collaboration (Stone et al., 2010; Taylor et al., 2011; Walsh et al., 2011; Barrett & Stone, 2012; Macindoe et al., 2012; Torrey & Taylor, 2013; Nikolaidis et al., 2015; Hadfield-Menell et al., 2016; Nikolaidis et al., 2017; Grover et al., 2018; Haug et al., 2018; Reddy et al., 2018; Wilson & Daugherty, 2018; Brown& & Niekum, 2019; Kamalaruban et al., 2019; Radanovic et al., 2019; Tschiatschek et al., 2019; Ghosh et al., 2020; Strouse et al., 2021). However, rather than developing algorithms that learn to switch control between humans and machines, previous work has predominantly considered scttings in which the machine and the human interact with cach other.
Finally, one can think of using option framework and the notion of macro-actions and micro-actions to formulate the problem of learning to switch (Sutton et al,, 1999). However, the option framework is designed to address different levels of temporal abstraction in RL by defining macro-actions that correspond to sub-tasks (skills). In our problem, each agent. is not necessarily optimized to act for a specific task or sub-goal but for the whole environment/gonn /gaal. Also, in our problem, we do not necessarily have control over all agents to learn the optimal policy for cach agent, while in the option framework, a primary direction to learn optimal options for each sub-task. In other words, even though we can mathematically refer to each agent policy as an option, they are not conceptually the same.
3

---

Published in Transations on Machine Learning Research (07/2022)
3
Switching Control Among Agents as a 2-Layer MDP
Given a team of agents D, at each time step E fi,...,,.y) Lt, our (cyberphysical) system is characterized by a state St E S, where is a finite state space, and a control switch d, E DD which determines who takes an action a2 E A, where A is a finite action space. In the above, the switch value is given by a (deterministic and time-varying) switching policy de = The d More specifically, if d, = d, the action az is sampled from the agent d's policy pa(ar st). Moreover, given state 8t and an action dt, the state 8 is sampled from a transition probability p(s(+1 (t, az). Here, assume that the agents' policies and the transition probabilities may be unknown. Finally, given an initial state and switch value (81, do) and trajectory = {(st, de, az) )== of states, switch values and actions, we define the total cost |[T|s] dg) as:
I dl 81, do) Eic((e, + celde) + cz de
(1)
where co(oe, ue) is the environment cost of taking action or at state St; Co(de) is the cost of giving control to agent di, Ca (d di-1) is the cost of switching from d-- to de, and is the time horizon'. Then, our goal is to find the optimal switching policy x² - = that minimizes the expected cost, i.C.,
n n²= argmin E [e(r 81; do)];
(2)
where the expectation is taken over all the trajectories induced by the switching policy given the agents' policies.
To solve the above problem, one could just resort to problem-agnostic RL algorithms, such as UCRL2 or Rmax, over a slandard Markov decision process (MDP), defined as
M (S x D, D. D,C,P,
where S x D is an augmented state space, the set of actions D is just the switch values, the transition dynamics P at time are given by
p($141, de st, d(-1) = (s), = del x
E((s Is, | (al (t).
(3)
acA
the immediate cost Ö at time & is given by
((s,,d-1) = Be, Pro 1el))) [ce(s), az)] + co( de-1)) + ex Ca (1-)))
(4)
Here, note that, by using conditional expectations, we can compute the average cost of a trajectory, given by Eq. 1, from the above immediate costs. However, these algorithms would not exploit the structure of the problem. More specifically, they would not use the observed agents' actions to improve the estimation of the transition dynamics over time.
To avoid the above shortcoming, will resort instead to 2-layer MDP where taking an action de in state (st, 1)-1) leads first to an intermediate state (st,at) E S x A with probability pa, (a, (8)) and immediate cost ca, (st, 1) = (o(d + cv (e dr-1) and then to a final state ($1+1, de) E S x D with probability [s,, d.-1) = d,1 p(s++1 st. a,) and immediate cost ce a.). More formally, the 2-layer MDP is defined by the following 8-tuple:
M MS A,D, PD. P, CC,,C.,,T)
(5)
where S is the final state space, Sx.A is the intermediate state space, the set of actions D is the switch values, the transition dynamics Pp and P at time t are given by Pa, (at st) and [[ de-1) = de] p(( a;, and the immediate costs Cp and C. at time are given by ca, (8t, d:-1) and ca (st, at), respectively.
The above 2-yer MDP will allow us to estimate separately the agents' policies pa(: 8) and the transition probability p(1 s, a) of the environment using both the intermediate and final states and design an algorithm that improves the regret that problem-agnostic RL algorithms achieve in our problem.
"Note that, by making the switching policy dependent on the previous switch value de-1, we can account for the awitching cost. 4Thh specific choice environment cost e (t()), control cost ee(:) switching cost oz -) application dopendent.
4

---

Published in Transations on Machine Learning Research (07/2022)
parlos)s)
par(agis)
pls11s, 0z) 0,02
8, d
8', s',d'
Der (Omls)
p(s
8, Omm
Switching Layer
Action Layer
Figure 1: Transitions of a 2-layer Markov Decision Process (MDP) from state (s, d) to state (s', d') after seleting agent d'. d' and denote the current and previous agents in control. In the first layer (switching layer), the switching policy chooses agent d', which takes action w.r.t. its action policy Pa- Then, in the action layer, the environment transitions the next state based on the taken action w.r.t. the transition probability p.
4 Learning to Switch in Team of Agents
Since we may not know the agents' policies nor the transition probabilities, we need to trade off exploitation, i.e., minimizing the expected cost, and exploration, i.e., learning about the agents' policies and the transition probabilities. To this end, look at the problem from the perspective of episodic learning and proceed follows.
We consider K independent subsequent episodes of length L and denote the aggregate length of all episodes as = KL. Each of these episodes corresponds to a realization of the same finite horizon 2-layer Markov decision process, introduced in Section 3, with state spaces policies Pe, true environment transition probability P", and immediate costs CD and C.. However, since do not know the true agent policies and environment transition probabilities, just before cach episode k starts, our goal is to find a switching policy n with desirable properties in terms of total regret R(T), which is given by:
and D, set actions D, true agent,
K R(T)
Σ
By P- (o(T 11,, do)] , P. [c(T $1, do)]
(6)
1=1
where T² is the optimal switching policy under the true agent policies and environment transition probabilitics. To achieve our goal, we apply the principle of optimism the face of uncertainly, i.e.,
n argmin min min Erom, [o(T s1,
(7)
PDEP PEPK
where Ph is (BSix()))L)rretangull confidence set, i.e., Ph X pk dds,, and pk (|) rectangular confidence set, i.e., pk = > a.,, Pk ",a,t" Here, note that the confidence sets are constructed using data gathered during the first it episodes and allows for time varyingying agent policies pa(: t) and transition probabilities p(. 8, 1)

---

Published in Transations on Machine Learning Research (07/2023
However, to solve Eq. 7, we first need to explicitly define the confidence sets. To this end, we first define the empirical distributions (-(-1s) 8) and f² ( a) just before episode l starts as:
Ng(a.d.))
if (4 d) 00 otherwise,
Pa(a s)=
Nuls.d)
(8)
[
Ny (s.a.e")
if (s, # otherwise,
(5' 18, (5'18,0))
(((o))
(9)
[S]
where
1-1
d) =
I(s: s.d. d in episode 1), N&(s, d,
I(s: -.0 = = = dd in episode 1),
I=1 LE
1=1 [E[L]
k-1
()(s,a)= Σ Σ
I(s: 8, in episode 1), N,(s,0,6)) = Σ
[[( 8, aa 8,411 = 8 in episode 1).
1=1
[=1
Then, similarly as in Jaksch et al. (2010), we opt for I confidence sets i.e.,
Pt (1), = { Pa [|pa(- s, P/ (1)ss)l
ph i (6) = { (p: Ipp( s,,,)) - p² (11,,)))l 8 (s, a, 8)}
for all d E D, 8 E S, a A and 1 E [T],, where given parameter,
(k- (K-1))177)110
2 2 (k- (M-11)277()))442244
2 2oo
8 (s,
and (s,a, = -
max [1, NN(
max (1, NN((,
Next, given the switching policy and the transition dynamics PD and P, we define the value function as
P = E +((c)a)) +c + dd(rr, st s. s, =d] =d].
(10)
where the expectation is taken over all the trajectories induced by the switching policy given the agents' policies. Then, for each episode k, we define the optimal value function of d) as
t (s, d) = min min min Va Pi
(11)
(d) PEP
Then, ready to use the following key theorem, which gives solution to Eq. 7 (proven in Appendix A): Theorem For any episode k, the optimal value. function vf (s, d) satisfies the following recursive equation:
(s, = min (a (s, diED
min
Epl(als, (,tls,)))x (x) min
Propt-Isa..lvii4 d..l)) (12)
na, EP Ideant aEA
PEPt mate
with ot i d) = for all s S and d D. Moreover, if di is the solution to the minimization problem of the RHS of the above recursive equation, then (s, di.
The above result readily implies that, just before each episode k starts, we can find the optimal switching policy * = (.f,..., TH) using dynamic programming, starting with (s, = 0 for all E S and E D. Moreover, similarly as Strehl & Littman (2008), we can solve the inner minimization problems Eq. 12 analytically using Lemma 7 in Appendix B. To this end, we first find the optimal p(- ss a, t) for all and
5mhis choice
sequence switching policies desirable proporties terms regret.

---

Published in Transations on Machine Learning Research (07 (07/2022)
ALGORITHM 1: UCRL2-MC
Cost functions CD and C.,
2: [N,, + INTIALIZECOUNTS()
3: for k 15==1.... I..... do
4:
1 <- UUDDATEDISTTBBUTONNNN.... N())
5:
Pp, pK + UFDATTECONPIENNSSSTSS((
6:
x² GETOOTTMAL(PSS PA CD. C.),
7:
(51, do) t INTIALIZECCONITTIONS))
for L....,L do
9:
di t- nt (s1,
at ~ (1188)
11:
8:41 ~ P(-|se, at)
N UUDATECOUUUSS(SSSdd.. 8441), N(H)
13: end for
end for
15: Return x
and then we find the optimal Pa, (-).)) for all de D. Algorithm summarizes the whole procedure, which refer to UCRL2-MC.
Within the algorithm, the function GETOPTIMAL() finds the optimal policy x* using dynamic programming, as described above, and UPDATEDISTRIBUUTON()) computes Eqs. 8 and 9. Moreover, it is important to notice that, in lines 8-10, the switching policy x² is actually deployed, the true agents take actions on the true environment and, as a result, action and state transition data from the true agents and the true environment is gathered.
Next, the following theorem shows that the sequence of policies {x* k== found by Algorithm 1 achieve total regret that is sublinear with respect to the number of steps, defined in Eq. 6 (proven in Appendix A);
Theorem 2. Assume we use Algorithm 1 to find the switching policies Th. Then, with probability at least 1 - 6, il holds that
(ISIDDIT)
|S||A| 5
R(T) S pity
|
paL|sly [A
(13)
where P1,22 > are constants.
The above regret bound suggests that our algorithm may achieve higher regret than standard UCRL2 (Jaksch et al., 2010), one the most popular problem-agnostic RL algorithms. More specifically, one can readily show that, if we use UCRL2 to find the switching policies x² (refer to Appendix C), then, with probability least 1 - 8, it holds that
|S|DI 8
R(T) pL|S| |D|T
(14)
where is constant. Then, if we omit constant and logarithmic factors and assumee the size of the team of agents is smaller than the size of state space, i.e., [D|< [S], we have that, for UCRL2, the regret bound is ((L)))V(P(T) while, for UCRL2-MC, is Ó(L)S) (AT)).
That being said, practice, we have found that our algorithm achieves comparable regret with respect UCRL2, as shown in Figure 4. In addition, after applying our algorithm specific team of agents and environment,
reuse the confidence intervals over the transition probability p(- s, a) have learned to find the optimal switching policy for different team of agents operating in a similar environment. In contrast, after applying UCRL2, we would only have a confidence interval over the conditional probability defined by Eq. 3, which would be little use to find the optimal switching policy for a different team of agents.
In the following section, we will build up on this insight by considering several independent teams of agents operating in similar environments. We will demonstrate that, whenever aim to find multiple sequences of

---

Published in Transations on Machine Learning Research (07/2022)
(a) 700 car
(b) 710 light
(c) 70 heavy
Figure 2: Three examples of environment realizations with different initial traffic level 70-
switching policies for these independent teams, straightforward variation of UCRL2-MC greatly benefits from maintaining shared confidence bounds for the transition probabilities of the environments and enjoys better regret bound than UCRL2
Remarks. For ease of exposition, we have assumed that both the machine and human agents follow arbitrary Markov policies that do not change due switching. However, our theoretical results still hold we lift this assumption we just need to define the agents' policies as palae]se de de-1) and construct separate confidence scts based on the switch values.
5 Learning to Switch Across Multiple Teams of Agents
In this section, rather than finding sequence of switching policies for single team of agents, we aim find multiple sequences of switching policies across several independent teams operating in similar environments. We will analyze algorithm in scenarios where it maintain shared confidence bounds for the transition probabilities of the environments across these independent teams. For instance, when the learning algorithm is deployed in centralized settings, it is possible to collect data across independent teams to maintain shared confidence intervals on the common parameters (i.e., the environment's transition probabilities in our problem setting). This setting fits a variety of real applications, more prominently, think of a car manufacturer continu collecting driving data from million of human drivers wishing learn different. switching policies for each driver to implement personalized remi-autonomous driving system. Similarly as in the previous section, look at the problem from the perspective of episodic learning and procced as follows.
Given N independent teams of agents (D:) consider K independent. subsequent episodes of length L per team and denote the aggregate length of all of these episodes as T = KL. For each team of agents D,, every episode corresponds to a realization of a finite horizon 2-layer Markov decision process with state spaces x AA and x D,, set of actions D,, true agent policies Pt. true environment transition probability p", and immediate costs CD, and C.. Here, note that all the teams operate similar environment, i.e., ps is shared across teams, and, without loss of generality, they share the same costs. Then, our goal is to find the switching policies o. with desirable properties in terms of total regret R(T, N), which is given by:
N R(T,N) = Σ
E B P P [e(T 81, do)] Ry po p- [o(T 81, (1, do)]
(15)
where प, is the optimal switching policy for team i, under the true agent policies and environment transition probability.
To achieve our goal, we just run N instances of UCRL2-MC (Algorithm 1), each with a different confidence set Pb, for the agents' policies, similarly as in the case of a single team of agents, but with shared confidence (*) for the environment transition probability. Then, we have the following key corollary, which readily follows from Theorem 2:
8

---

Published in Transations on Machine Learning Research (07 (07/2022)
(a) Co 0.1, ca ca(LL) = 0.2
(b) cu = 0, (H = 0
Figure Trajectories induced by the switching policies found by Algorithm 1. The blue and orange segments indicate machine and human control, respectively. In both panels, we train Algorithm 1 within the same sequence of episodes, where the initial traffic level of each episode is sampled uniformly from {no-car, light, heavy), and show three episodes with different initial traffic levels. The results indicate that, in the latter episodes, the algorithm has learned to switch to the human driver in heavier traffic levels.
Corollary 3. Assume we use N instances of Algorithm 1 to find the switching policies n. using a shared confidence set for the enwironment transition probability. Then, with probability at least 5, it holds that
|S||A|T 8
R)T,N) S PINL |l|S||D|T
P2L15|
L log
(16)
where Pl,P2 > are constants.
The above results suggests that our algorithm may achieve lower regret than UCRL2 in a scenario with multiple teams of agents operating in similar environments. This is because, under UCRL2, the confidence sets for the conditional probability defined by Eq. 3 cannot be shared across teams. More specifically, we use N instances of UCLR2 to find the switching policies nh then, with probability least 1-5, 8, it holds that
|S|DIT
R(T, N) S PNLIS |D|Tlog
where is a constant. Then, if we omit constant and logarithmic factors and assume |D:|< |S] for all E [N], we have that, for UCRL2, the regret bound is ((NL/S)//PI7) while, for UCRL2-MC, it is Importantly, in practice, we have found that UCRL2-MC does achieve
ÖLLS V AATN + / significant lower regret than UCRL2, as shown in the Figure 5.
6
Experiments
6.1 Obstacle avoidance
We perform a varioty of simulations in obstacle avoidance, where teams of agents (drivers) consist of one human agent (IH) and one machine agent (MI), i.e., D = {H, M). We consider lane driving environment with three lanes and infinite rows, where the type of each individual cell (f.e. road, car, stone or grass) in row is sampled independently at random with a probability that depends on the traffic level Yr. which can take three discrete values, 7r {no-car, light, heavy). The traffic level of each row 7r+1 is sampled at random with a probability that depends on the traffic level of the previous row 7-- The probability of each cell type based on traffic level, as well as the conditional distribution of traffic levels can be found in Appendix D.
At any given time t, we assume that whoever is control- be it the machine the human can take three different actions A {left, straight, right). Action left steers the car to the left of the current lane,
9

---

Published in Transations on Machine Learning Research (07/2022)
x10
x x10
75
UCRL2-MC
UCRL2-MC
Regret, R(T)
UCRL2
Regret, R(T)
UCRL2
50
Machine
Machine
50
Human
Human
25
0
5
10
15
20 x10*
0
5 10
15
20
Episode, l
Episode, k
x 10
(a) (H)) 0.2, Co 0.1
(b) (H) 0, cr
Figure 4: Total regret of the trajectories induced by the switching policies found by Algorithm and those induced by variant of UCRL2 in comparison with the trajectories induced by a machine driver and a human driver in a setting with a single team of agents. In all pancls, we run K = 20,000. For Algorithm and the variant of UCRL2, the regret is sublinear with respect to the number of time steps whereas, for the machine and the human drivers, the regret is linear.
action right steers it to the right and action straight leaves the car in the current lane. If the car is already on the leftmost (rightmost) lane when taking action left (right), then the lane remains unchanged. Irrespective of the action taken, the car always moves forward. The goal of the cyberphysical system is to drive the car from an initial state in time L = 1 until the end of the episode t = L with the minimum total amount of cost. In our experiments, we set T, = 10. Figure 2 shows three examples of environment realizations.
State space. To evaluate the switching policies found by Algorithm 1, we experiment with a sensor- state space, where the state values are the type of the current cell and the three cells the car can move into in the next time step, as well as the current traffic level-we assume the agents (be it a human or a machine) can measure the traffic level. For example, assume at time the traffic is light, the car is on road cell and, if it moves forward left, it hits stone, if it moves forward straight, it hits car, and, if it moves forward right, it drives over grass, then its state value is s, (light, road, stone, car, grass). Morcover, if the car is on the leftmost (rightmost) lane, then we set the value of the third (fifth) dimension in st to 0. Therefore, under this state representation, the resulting MDP has ~3 x 5 states.
Cost and human /machine policies. We consider state-dependent enviromment cost ca(se, a.) cx(s that depends on the type of the cell the car is on at state 8t, i.e., Ca (s:)) if the type of the current cell is road, (st) = 2 if it is grass, ce(s)) = 4 if it is stone and (s:):) 10 if it is car. Moreover, in all simulations, we use a machine policy that has been trained using a standard RL algorithm on environment realizations with "0 no-car. In other words, the machine policy is trained to perform well under a low traffic level. Moreover, we consider all the humans pick which action to take (left, straight or right) according to a noisy estimate of the environment cost of the three cells that the car can move into in the next time step. More spocifically, cach human model computes a noisy estimate of the cost (s( = (s()) + Gg of cach of the three cells the car can move into, where 6, (O,, and picks the action that moves the car to the cell with the lowest noisy estimate As result, human drivers are generally more reliable than the machine under high traffic levels, however, the machine is more reliable than humans under low traffic level, where its policy is near-optimal (See Appendix E for a comparison of the human and machine performance). Finally, we consider that only the car driven by our system moves in the environment.
6.1.1 Results
First, we focus on a single team of one machine M and one human model H, with dg = 2, and use Algorithm to find sequence of switching policies with sublinear regret. At the beginning of each episode, the initial traffic level % is sampled uniformly at random.
6 Note that, our theoretical results, we have no assumption other than the Markov property regarding human policy.
10

---

Published in Transations on Machine Learning Research (07/2022)
x10
x x10
60
UCRL2-MC
UCRL2-MC
UCRL2
UCRL2
Regret, R(T)
Regret, R(T)
40
40
20
20
0
01
2
0
Episode, l
x10
Episode, A
x x10
(a) (H)) 0.2, Co 0.1
(b) (H(H) 0,
Figure 5: Total regret of the trajectories induced by the switching policies found by N instances of Algorithm and those induced by N instances of variant of UCRL2 in setting with N team of agents. In both panels, each instance of Algorithm 1 shares the same confidence set for the environment transition probabilities and we run K = 5000 episodes. The sequence of policies found by Algorithm 1 outperform those found by the variant of UCRL2 in terms of total regret, in agreement with Corollary 3.
We look at the trajectories induced by the switching policies found by our algorithm across different episodes for different values of the switching cost C₂ and cost of human control c. (H)). Figure 3 summarizes the results, which show that, in the latter episodes, the algorithm has learned to rely the machine (blue segments) whenever the traffic level is low and switches to the human driver when the traffic level increases. Moreover, whenever the amount of human control and number of switches is not penalized (i.e., Ce ce (HH)) 0), the algorithm switches to the human more frequently whenever the traffic level is high to reduce the environment cost. See Appendix for a comparison of humna control rale in environments with different initial trallic levels.
In addition, we compare the performance achieved by Algorithm 1 with three basclines: (i) a variant of UCRL2 (Jaksch et al., 2010) adapted to our finite horizon setting (see Appendix C), (ii) human agent, and (iii) machine agent. As measure of performance, we use the total regret, as defined in Eq. 6. Figure 4 summarizes the results for two different values of switching cost ea and cost of human control colll.. The results show that both our algorithm and UCRL2 achieve sublinear regret with respect to the number of time steps and their performance is comparable in agreement with Theorem 2. In contrast, whenever the human or the machine drive on their own, they suffer lincar regret, due to a lack of exploration.
Next, we consider N 10 independent leams of agents, (D.) operating in a similar lane driving environment. Each team D, is composed of different human model Hl, with σh, sampled uniformly from (0, 4), and the same machine driver M. Then, to find sequence of switching policies for cach of the tcams, we run N instances of Algorithm 1 with shared confidence set for the environment transition probabilities.
We compare the performance our algorithm against the same variant of UCRL2 used in the experiments with a single team of agents in terms of the total regret defined in Eq. 15. Here, note that the variant of UCRL2 does not maintain a shared confidence set for the environment transition probabilities across teams but instead creates confidence set for the conditional probability defined by Eq. 3 for each team. Figure 5 summarizes the results for sequence for different values of the switching cost e, and cost of human control ce (HH), which shows that, in agreement with Corollary 3, our method outperforms UCRL2 significantly.
6.2 RiverSwim
In addition to the obstacle avoidance task, we consider the standard task of RiverSwim (Strehl & Littman, 2008). The MDP states and transition probabilities are shown in Figure 6. The cost of taking action in states $2 to 85 equals 1, while 0.995 and 0 for states $1 and s6, respectively. Each episode ends after = 20
7 HHrr, we assume the cost of machine control (M)
11

---

Published in Transations on Machine Learning Research (07/2022)
0.4
116
0.6
016
0.6
0.6
0.35
Q
0.35
0.35
0.35
0.05
0.05
0.05
0.05
$6
0.4
86
0.6
Figure 6: RiverSwim. Continuous (dashed) arrows show the transitions after taking actions right (left). The optimal policy
always take action right.
X 10
200
UCRL2-MC
Regret Ratio
0.4
Regret, R(T)
UCRL2
0.2
100
0.0
0.0
2.5
5.0
10.0
Number of Teams
Episode, k
x10
(a)
(b)
Figure (a) Ratio of UCRL2-MC regret to UCRL2 for different number teams. (b) Total regret of the trajectories induced by the switching policies found by UCRL2-MC and those induced by UCRL2 in a setting with N = 100 team of agents.
steps. We set the switching cost and cost agent control to zero for the simulations in this section, iee, cx(:-) ce(-) O. The set D consists of agents that choose action right with some probability value p. which may differ for different agents. In the following part, investigate the effect of increasing the number of teams the regret bound in the multiple teams of agents setting. See Appendix G for more simulations to study the impact of action size and nunber of agents in each team the total regret.
6.2.1 Results
We consider N independent teams of agents, each consisting of two agents with the probability p and p of choosing action right, where p is chosen uniformly at random for cach team. We run the simulations for N = (3, ..., 10) teams of agents. For each N, we run both UCRL2-MC and UCRL2 for 20,000 episodes and repeat each experiment times. Figure (a) summarizes our results, showing the advantage of the shared confidence bounds on the environment transition probabilitics in our algorithm against its problem-agnostic version. better illustrate performance of UCRL2-MC, we also run an experiment with = 100 teams of agents for 10,000 episodes and compare the total regret of our algorithm to UCRL22 Figure (b) shows that our algorithm significantly outperforms UCRL2.
7 Conclusions and Future Work
We have formally defined the problem of lcarning switch control among agents in a team via 2-layer Markov decision process and then developed UCRL2-MC, an online learning algorithm with desirable provable guarantees. Moreover, have performed variety of simulation experiments the standard RiverSwim task and obstacle avoidance to illustrate our theoretical results and demonstrate that, by exploiting the specific structure of the problem, our proposed algorithm is superior to problem-agnostic algorithms.
Our work opens up many interesting avenues for future work. For example, we have assumed that the agents' policies are fixed. However, there are reasons to believe that simultancously optimizing the agents' policies and the switching policy may lead to superior performance (De al., 2020; 2021; Wilder et al., 2020; Wu et al., 2020). In work, have assumed that the state space is discrete and the horizon in finite. It.
12

---

Published in Transations on Machine Learning Research (07/2022
would be very interesting to lift these assumptions and develop approximate value iteration methods to solve the learning to switch problem. Finally, it would be interesting to evaluate our algorithm using real human agents in a variety of tasks.
Acknowledgmennts. Homez-Rodrrguez acknowledges support from the European Research Council (ERC) under the European Union's Horizon 2020 rescarch and innovation programme (grant agreement No. 945719).
References
Samuel Barrett and Peter Stone. An analysis framework for ad hoc teamwork tasks. In Proceedings of the 11th International Conference on Aulonomous Agents and Mulliagent Systems- Volume 1, pp. 357-364, 2012.
P. Bartlett and M. Wegkamp. Classification with a reject option using a hinge loss. JMLR, 2008
K. Brookhuis, D. De Waard, and W. Janssen. Behavioural impacts of advanced driver assistance systems an overview. European Journal of Transport and Infrastructure Research, 1(3), 2001.
Daniel S Brown and Scott Niekum. Machine teaching for inverse reinforcement learning: Algorithms and applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7749-7758, 2019.
C. Cortes, G. DeSalvo, and M. Mohri. Learning with rejection. In ALT, 2016.
Mary Czerwinski, Edward Cutrell, and Eric Horvitz. Instant messaging and interruption: Influence of task type on performance. In OZCHI 2000 conference proceedings, volume 356, pp. 361-367, 2000.
Nathaniel D. Daw and Peter Dayan. The algorithmic anatomy of model-based evaluation. Philosophical Transactions of the Royal Society B: Biological Sciences, 369(1655):2013477, 2014.
A. De, P. Koley, N. Ganguly, and M. Gomez- Rodrig-o. Regression under human assistance. In AAAI, 2020.
Abir De, Nastaran Okati, Ali Zarezade, and Manuel Gomez-Rodriguee Classification under human assistance.
AAAT, 2021.
European Parliament. Regulation (EC) No 561/2006. http:///btta.ummpppee///////// /000://00200006661//155000002 2006.
R. Everett and S. Roberts. Learning against non-stationary agents with opponent. modelling and deep reinforcement learning. In 2018 AAAI Spring Symposium Series, 2018.
Y. Geifman and R. El- Yaniv. Selectivenet: A deep neural network with an integrated reject option. arXiv preprint trXi::1901.0919, 2019.
Y. Geifman, G. Uziel, and R. El-Yan Yaniv.. Biascreduced uncertainty estimation for deep neural classifiers. In ICLR, 2018
A. Ghosh, S. Tschiatschck, H. Mahdavi, and A. Singla. Towards deployment of robust cooperative ai agents: An algorithmic framework for learning adaptive policies. In AAMAS, 2020.
Aditya Gopalan and Shie Mannor. Thompson sampling for learning parameterized markov decision processes. In Conference on Learning Theory, pp. 861 11-8888855 2015.
A. Grover, M. Al-Shedivat, J. Gupta, Y. Burda, and H. Edwards. Learning policy representations in multiagent systems. In ICML, 2018.
D. Hadfeeld-Mnnell, S. Russell, P. Abbeel, and A. Dragan. Cooperative inverse reinforcement learning. In NIPS, 2016.
L. Haug, S. Tschiatschek, and A. Singla. Teaching inverse reinforcement learners via features and demonstra- tions. In NewrIPS, 2018.
13

---

Published in Transations on Machine Learning Research (07/202)
Eric Horvitz and Johnson Apacible. Learning and reasoning about interruption. In Proceedings of the 5th international conference on Multimodal interfaces, pp. 20-27, 2003.
Shamsi T Iqbal and Brian P Bailey. Understanding and developing models for detecting and differentiating breakpoints during interactive tasks. In Proceedings of the SIGCHI conference on Human factors in computing systems, pp. 697 706, 2007.
Alexis Jacq, Johan Ferret, Olivier Pictquin, and Matthicu Geist. Lazy-mdps: Towards interpretable reinforcement learning by learning when to act. In AAMAS, 2022.
Jaksch, R. Ortner, and P. Auer. Ncar-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 2010.
Christian P Jansson, Shamsi T Iqbal, Andrew L Kun, and Stella F Donker. Interrupted by my car? implications of interruption and interleaving research for automated vehicles. International Journal of Computer Studies, 130:221-201 233, 2019.
Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive teaching algorithms for inverse reinforcement learning. In IJCAI, 2019.
Kyle Kotowick and Julie Shah. Modality switching for mitigation of sensory adaptation and habituation in personal navigation systems. In 23rd International Conference on Intelligent User Interfaces, pp. 115 127, 2018.
Z. Liu, Z. Wang, P. Liang, R. Salakhutdinov, L. Morency, and M. Ueda. Deep gamblers: Learning abstain with portfolio theory. In NewrIPS, 2019.
C. Macadam. Understanding and modeling the human driver. Vehicle system dynamics, 40(1-3):101 134, 2003.
O. Macindoe, L. Kaelbling, and T. Lozano-Péren Pomcop: Belief space planning for sidekicks in cooperative games. In ATIDE, 2012.
Catharine L. R. McGhan, Ali Nasir, and Ella M. Atkins. Human intent prediction using markov decision processos. Journal of Aerospace Information Systems, 12(5):393-38) 397, 2015.
V. Mnih et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Salama Mostafa, Mohd Sharifuddin Ahmad, and Aida Mustapha. Adjustable autonomy: a systematic literature review. Artificial Intelligence Review, 51(2):149 1114499--6666111 2019.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In ICML, 2020.
S. Nikolaidis, R. Ramakrishnan, K. Gu, and J. Shah. Efficient model learning from joint-action demonstrations for human-robot collaborative tasks. In HRI, 2015.
S. Nikolaidis, J. Forlizzi, D. Hsu, J. Shah, and S. Srinivasa. Mathematical models of adaptation in human-robot collaboration. ar preprint wwXiv:1777.02550 2017.
Ian Osband and Benjamin Van Roy. Near-optimal reinforcement lcarning in factored mdps. In Advances in Neural Information Processing Systems, pp. 604 612, 2014.
Ian Osband, Danicl Russo, and Benjamin Van Roy. (more) efficient reinforcement lcarning via posterior sampling. In Adoances in Neural Information Processing Systems, pp. 3003 3011, 2013.
Goran Radanovic, Rati Devidze, David C. Parkes, and Adish Singla. Learning to collaborate in markov decision processes. In ICML, 2019.
M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, and S. Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort. arXiv preprint or orXiv:1000 12220, 2019a.
14

---

Published in Transations on Machine Learning Research (07/2022)
M. Raghu, K. Blumer, R. Sayres, Z. Obermeyer, B. Kleinberg, S. Mullainathan, and J. Kleinberg. Direct uncertainty prediction for medical second opinions. In TCML, 2019b.
H. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic J. of Statistics, 2018.
Siddharth Reddy, Anca D Dragan, and Sergey Levine. Shared autonomy via deep reinforcement learning. arXiv preprint vrXit:1802.017// 2018.
Shubhanshu Shekhar, Mohammad Ghavamzadeh, and Tara Javidi. Active learning for classification with abstention. TEFE Journal on Selected Areas in Information Theory, 2(2):705- 719, 2021.
D. Silver et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
D. Silver et al. Mastering the game of go without human knowledge. Nature, 550(7676):354. 2017.
Peter Stone, Gal A Kaminka, Sarit Kraus, and Jeffrey S Rosenschein. Ad hoc autonomous agent teams: Collaboration without pre-coordination, In Tuenty-Fourth AAAI Conference on Artificial Intelligence, 2010.
A. Strehl and M. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309 1331, 2008.
DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. Collaborating with humans without human data. In Advances in Neural Information Processing Systems, volume 34, 2021.
Richard S Sutton, Doina. Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-22 2211, 1999.
Matthew E Taylor, Halit Bener Suay, and Sonia. Chernova. Integrating reinforcement learning with human demonstrations of varying ability. In The 10th International Conference on Automomous Agents and Mulliagent Systems- Volume 2, pp. 617 624. Internations ional Foundation for Autonomous Agents and Multiagent Systems, 2011.
S. Thulasidasan, T. Bhattacharya, Bilmes, G. Chenmupati, and Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint ar arXiv:1905.11000 2019.
Lisa Torrey and Matthew Taylor. Teaching on budget: Agents advising agents in reinforcement learning. In Proceedings of the 2013 international conference on Aulonomous agents and mulli-ogent systems, pp. 1053-1060 2013.
James T. Townsend, Kam M. Silva, Jesse Spencer-Smithe and Michael J. Wenger. Exploring the relations between categorization and decision making with regard to realistic face stimuli. Pragmatics & Cognition, 8(1):83-105, 2000.
S. Tschiatschek, A. Ghosh, L. Hang. R. Devidze, and A. Singla. Learner-aware teaching: Inverse reinforeement learning with preferences and constraints. In NewrIPS, 2019.
O. Vinyals et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, pp. 1-5, 2019.
Thomas Walsh, Daniel K Hewlett, and Clayton T Morrison. Blending autonomous exploration and apprenticeship learning. In Advances in Neural Information Processing Systems, pp. 2258-2266 2011.
Bryan Wilder, Eric Horvitz, and Ece Kamar. Learning to complement humans. In IJCAI, 2020.
H. Wilson and P. Daugherty. Collaborative intelligence: humans and ai are joining forces. Harvard Business Review, 2018.
15

---

Published in Transations on Machine Learning Research (07/2022)
Bohan Wu, Jayesh K Gupta, and Mykel Kochenderfer. Model primitives for hierarchical lifelong reinforcement learning. Autonomous Agents and Mulli-Agent Systems, 34(1):1-35 2020.
Y. Zheng, Z. Meng. Hao, Z. Zhang, T. Yang, and C. Fan. A deep bayesian policy reuse approach against non-stationary agents. In NewrIPS, 2018.
16

---

Published in Transations on Machine Learning Research (07/2022)
A Proofs
A.1 Proof of Theorem 1
We first define Ph Dj..et == "EE P. P.l....s Id,,,'' Pf. = d Ple Ps,a, and Ty+
{me..... [ Next, we get a lower bound the optimistic value function of (s,d) as follows:
m.).
(s,
-min min min Vi p(s,)
PDEPs PEP
= -min min min
Vi (ilp,r(ss,d)
PoEPs PEpe
(1)
min
min () oe pl.....))P) lone
min
m((ad)
(xx(e,,))8) d) + E Ba- (co(s.a) + Belppt-1sa. V Vttr me d))]
min
F(++))-
PoEPb D1
PEP --a+t)+
(i))
min
min
min p(ls..,)Ep
(r.(e,d) (8,
ni (5.d) (s.te meleaaa
+Bu-praes co(s,a) + (pslpp(-sa,a)
min Ee+tyy Poept
min
min 1.0++4+
1o p(d nr((s,)) ((5,
PI Dl.at++) Pep
min de
cd. (s, d) +
min pa, (EP
Σ pa (als,t) dldsiet aeA
(c((s,))+
+
min p(.l,,,,))PP
Es Laape
where (i) follows from Lemma 8 and (ii) follows from the fact that min, B[X(a)) Flmin,, X(a)). Next, we provide an upper bound of the optimistic value function of d) as follows:
of (s,
min min min PDEPL PEPE
Vo d)
min (aat)) Incesasien
min
min pl p(ll...))PP 1 Jana
(Galan) d) + Barpaaan (co(s,a) + Eg ), a. P() d)))
min a(-++
PoEP PDEPP-ODD
PEP 11.0)
(1))
min
min
(((3d)
min p(le...)) Tamt
(s, +Eu-pa (ce(s, + Es s ( Vir (5 m((.
(18)
min me(a.))
min
(n(ss +E + (ca(s,a) + Ex sa Tr(s, d))]
min p)le..))ePt
Ex 14000)) (6f,aa)) .a1)
min de
cd, (s, d) +
min
E pa. (als,t) (e(
min p(la,a,))P san
pa, (l
Me REA
17

---

L Published in Transations on Machine Learning Research (07/2022)
Here, (i) follows from Lemma 8, (ii) follows from the fact that:
min "( PoeP P1-ain+ PEP 1104+))
(ms(s,a) d) + Bompescnn) (co(s, ()) + Bx I...) V4 P(l
$ (Cc(oad) + Earpr (e((8, + 1aa
Vu, PD E Pk
D D) PE Pk -11(++1+
(17)
and if we set *(4+1)+ = ( ";), PD PB E Ph
D1-(+1)1 and P= P E P1-(00))) where
Ti. (
argmin -((+))-
V (=
(18)
PoeP PoEPai-a-n) d1-te1)
PEP ---ttty
then equality (iii) holds. Since the upper and lower bounds are the same, conclude that the optimistic value function satisfies Eq. 12, which completes the proof.
A.2 Proof of Theorem 2
In this proof, assume that as) Ce(d) + (x,dd") < for all E S,a E A and d, d, E D. Throughout the proof, we will omit the subscripts P P in Vi rr and write V, instead in case of true agent policies PT and true transition probabilities pa Then, we define the following quantities:
p argmin min ViP P(T, do).
(19)
(B) (E)
ph argmin (irggr(s1..0) do), (5)
(20)
A = Vi" do) - Vi (s1, do).
(21)
where, recall from Eq. 7 that, x² argmin, minp minpep* Vijpo,r ($1, do); and, A indicates the regret for episode Hence, we have
R(T) Σ A Σ
E Ph) + Σ ART(PS PS V PP)
(22)
Next, split the analysis into two parts. We first bound ΣK ART(P) E Pp P* E phi and then bound E AMI(Ps & Ph v v & Ph).
Computing the bound on Ek A
First, we note that
A = (81, - VT (s), S Vi** (81, Vx*
pt (81,
(23)
This is because
(1) (6) min min min ViT ViPpor(Si,de do) S min V
- 1 pe (81, do)
= Vi (51, do),
(24)
PoEPS PePs
where (i) follows from Eqs. 19, 20, and (ii) holds because of the fact that the true transition probabilities V**
Pe E Ph and p* :p. Next, we use Lemma 4 (Appendix B) to bound I (s1, lipg. pt (81, do)).
K
k
L
(V (s1, (o) - y=² 1|pg (51, do)) <
LIE
min(1, (s,, de, 8)} + Σ
min(1 (s,, as), $1 do
t=1
(25)
18

---

Published in Transations on Machine Learning Research (07/2022)
Since by assumption, (e(s, ce(d) cd < for all S,a A and d, D, the worst-case regret is bounded by T. Therefore, we have that:
K ( E PB A p E EP*) & min
K
T,
LE
min 1, (st, de 8)H|s, do
k=1
LE
min (s a1 6)) do
K
L
min
T,
LE
min 1 de, 8)Hl8,, do
k=1
+ min
T.
LE
min (1, 1 (s.. ae 8)H|81, do
(26)
k=
where, the last incquality follows from Lemma 9. Now, we aim to bound the first term in the RHS of the above inequality.
K
L
K
L
2 log
((k- (18-))))($|1111214
(
LE
min 1in(11,8(ss de 8)}|81, do
L
E
min
1,
81, do
max (1, (Ns d:)
(KD))S/11/221111
2 log 1,
L
E
Σ
min
11 de)
1=
1=1
(18)
(KL))
S 2/2L
2log
(S||D|K
+
(27)
(KL)S)) D
S 22
14|A
[SID)KL+2L
(KL)SIII)
v112
|Allog
|S| 21
(28)
where (i) follows by replacing (5,, de, 8) with its definition, (ii) follows by the fact that (k: - 1)L S KL, (iii)
follows from Lemma 5, in which, we put : = SxD,e c 22log (KL))IS) ) Ta (wk, WK.L) =
((s), di), (s1, dz.)). Now, due to Eq. 28, we have the following.
K
min (1, (s,, d, 8)) do ]
S min { Tr, v 112L
T
min T,
Σ
smin
|
+ 2222|S|D2
8
k=1
(29)
Now, iT S 212
T
T|8 [D]
T < 21" (1AID/T
T v2L
|T log
5
19

---

Published in Transations on Machine Learning Research (07/202)
T and Tf> ||
8
|L log D
T
2L2|
/ D/
V2L
(30)
||lo
D
Thus, the minimum in Eq. 29 is less than
(v2+ ( SIAAIIIIIO log (5)
(
|
< 12L |S|AA|
(31)
5
A similar analysis can be done for the second term of the RHS of Eq. 26, which would show that,
LE Σ min (st, ae, 8)H[s, do }| 12//Sl1/ | log
TISIAA
min Tr>nn
(32)
k=1
Combining Eqs. 26, 31 and 32, we bound the first term of the total regret follows:
(TS||ID)
(T16)
(TSS|IA))
ANI(PS E P / Al|S]|D|Tlog
12L/S|
(33)
8
Computing the bound on Σ ART(P' & P V P P*)
Here, we use similar approach to Jaksch et al. (2010). Note that
E
AII(Ps P Pa pPh) Σ
A V E
Σ
A & P.VP Ph).
+1
(34)
Now, our goal is to show the second term of the RHS of above equation vanishes with high probability. we succeed, then it holds that, with high probability, Σk A&T(P5 & P$ v p & pP) equals the first term of the RHS and then we will be done because
V
(
K
A.T
EPH
Σ
A
= VKT.
(35)
L
where (i) follows from the fact that A < L since we assumed the cost of each step cs a) +c < 1
for all s E S, a E A, and d, E D.
To prove that Σk
k= I= +1 & E ph) = with high probability, we proceed as follows. By
applying Lemma 6 to D and Pr, we have
8 v
Pr(Pp
Pr(P" PK) s
(36)
21. 8,
21
Thus,
8
Pr(P: E P v Pt EPP < Pr(Ps & P$)
Pr(P" & pkk
(37)
20

---

Published in Transations on Machine Learning Research (07/202)
where ts (k- - 1)L is the end time of episode l 1. Therefore, it follows that
Pr
A & P V P P -0) Pr
0)
vk
K
+
+isks
PS PEEPA EPI
L
1 Pr
3h: [V
+1 P p
Σ
Pr(P & V P PP")
k=
+1
(6)
K Σ
2
k=
+1
(68)
KL
5
8 VRT
KL
8
(38)
16
8
5(KL)
KL
where (i) follows from union bound, (ii) follows from Eq. 37 and (iii) holds using that (l: 1) Hence, have that
with probability at least 1 5(KL)
& V Pa P =0 O.
(39)
If we combine the above equation and Eq. 35, we can conclude that, with probability at least 1 have that
57w/4, we
Σ
ARI(PS & EP)
(40)
where T = LL. Next, if we combine Eqs. 33 and 40, we have
K R(T) = Σ T E
K PP +
ART(PT & P V P Pt
1=1
T
TIS|AA|
12L
|||S]| log
12
|A|T log
VT
8
T
T|S
< 13L |A|ST|D|TIog log
+ 12L/5/
|A|T log
(41)
8
Finally, since Σ 57 S 8, with probability at least 8, the above inequality holds. This concludes the proof.
B Useful lemmas
Lemma 4. Suppose PD and P are true transitions and Pd E Ph, PE pk for episode k. Then, for arbitrory policy t and arbitrary PhS E pl, pk pPk,, it holds that
H
V P(),o, d) Ps (s, < L...
min (1, 2 (st. 8)} + Σ
min (1, ( at, 8)} 11 = = = d
(42)
21

---

Published in Transations on Machine Learning Research (07/2022)
where the expectation is taken over the MDP with policy x² under true transitions Pb and P.
Proof. For ease of notation, let vt = Vit Po.p, uiix= Vaa pl pu and (s, = (8) d). We also define d' (s, d). From Eq 68, we have
(s) = ds(s,)) Σ
Pat(aa)(al8)) co(s,a)+ + En('ls,a) (
(43)
aEA
#'ES
() = (s, +
Σ
pa Pattaaa(aal)) (als) (o(s,a)+ Σ (d'ls,) (
(44)
REA
e'ES
Now, using above equations, we rewrite - (
ds - (s)
Σ
Patton
co(s.a)+ + Σ
p(s -
aeA
d'S
ph Pattan Ce(s,a)+ + Er a) - (2))
aEA
s'ES
(
Σ (als) ce(s,a)+
Σ
p( u - -c(o,,a) - (aaa)-Erte (s((8))) (s) o (8ja((.
AEA
eESS
e'ES
+ Σ
(Pat(eag(alls) - - (als)
co(s,a)+ ((ssa))+++ee
T (2
DEA
e'ES
St.
(16)
(at(saa(aas)) Σ 116((1), s,
| (, dr)
REAA
s'ES
L
Σ
(attoa)(aas)) ph Pat(any(aa11)
aEA
Σ
3'ES (af(oa)(a18))
Eplsl
p(s)lo,,a) 18,a). (1)())() d1) wb (
p(s'
+ Σ
Pat(oa)(aas)) 8) Σ
(p(s (8,a) (s'' s,))) 2nt (s')
.EA
S'ES
L Σ
1 (attonn(alss) Dt (e, (alo)))))))))
aEA
(ie)
E Ea-p Pa (11)))s 1s.0) T5(s' d') - (5)1((8'd') dd]
+ LE an (1
Σ [p(s'|s,a) - (5 [|]]] + Σ
(rt(ea)(alss)
pet (a (als)]
LES
aEA
(45)
where (i) follows by adding and subtracting term (at(a.) 8) [e (s,a) Th T d')) (ii) follows from the fact that ce + Es (s' s a) (s (d) + cz d') for all s E S, A and d, d' D.. Similarly, (iii) follows by adding and subtracting p(s' (s)) (o', d'), and (iv) follows from the fact that u I L. By assumption, both Pp and Ph lie in
(s'(s'dd)) d') since, by assumption, ce(s, +
22

---

Published in Transations on Machine Learning Research (07/2022)
the confidence set PB (d), so
Σ REA
(o (al P Pat(an)(als)) s (in(,, =f((,
(46)
Similarly,
Σ [p(s' 88 - [a) z 6)}
(47)
e'ES
If we combine Eq. 46 and Eq. 47 in Eq. 45, for all S, it holds that
(s (0,
Bamp,ton oo
[2 d') o x d')
+ LB Laa (1s) [min 8 a, 5)H]
L |min (1, (b, (s,
(48)
Similarly, for all E S, d D we can show
(s Th ds s ( V5(s's 12(s, d)) Ty (s' (sss =2(,
+ L pp
L [min (1, (b (s, (s.
(49)
Hence, by induction we have
of - (s, LE Σ min
(5, 1,
de, 8)} + Σ m (s,, 0)Hls1 s, d)
(50)
where the expectation is taken over the MDP with policy x under true transitions PD and P.
Lemma 5. Let W be finite set and be a constant. For & E [K], suppose Ta = [[W,,1, Wk.2 Wk.H) is random variable with distribution P(-lwa.), where Wk,i E W. Then,
Σ P((ee.))
Σ min
221W1+2/222/11KT
(51)
max(1, 1, (u(
with Na(w) == E EM Mwja w).
Proof. The proof is adapted from Osband et al. (2013). We first note that
K
H
K
H
E
min
=
E
T(Na(u S H) min v /mxx{ [1, Ne(wu..))
/max (1, Na
K
+ E
I(N&(wk.1) H) min(1 /max(11 1, No (wwke)))
K
H
<
K
H
+ E
((Na(w).)) H)
(52)
Nu (wkk))
23

---

Published in Transations on Machine Learning Research (07/2022)
Then, we bound the first term of the above equation
H
E
I(Nu(wn,)) S H)
E
Σ { of times w is observed and N&(w) s H1}
WEW
[1 2H WW
(33)
bound the second lerm, we first define ny (w) as the number of times w has been observed the first r steps, (.e., if we are the tth index of trajectory Th, then 7 = ty + t, where to (k 1)H, and note that
nu++((w) (2(w)) +t
(54)
because we will observe w at most E {I...., H} times within trajectory Th. Now, if N&(w) H, we have that
n Ma+r(w)+15 Ne(w) +t+1s Ne(w)) + + + 2Nx(w..
(55)
Hence we have,
I(Ne(wn,)) H) Ne((w,))
((N+(wR.)) H)(mt + 2N (Wa,e)
(56)
De (Wert
Then, using the above equation, we can bound the second term in Eq. 52:
II ((Na) > H)
E
I(N((w,.)> > H)
E
V
Nu (1CKe)
(i)
K
H
V2cE
ΣΣ
(57)
mestoluke)) +
where (i) follows from Eq. 56.
Next, we can further bound E
as follows:
k=
t==1
KH
(wkk) +1
n2 (wT) +1
Nxw
E
WEW
W
NK-1(w)
1
Σ
E
Σ
++1
wEW
NK)+(10)+1
Σ
E
dx
x NK+1(w)
WEW
Σ
2
wEW
(#))
IE
2
W Σ Nk+1(w)
(126) EE
2 WW// 2 [WIKH, (58)
wEW
where (1) follows from summing over different w E W instead of time and from the fact that we observe each w exactly NK+1(w) times after K trajectories, (ii) follows from Jensen's 's incquality and (iii) follows from the fact that. Enew N = K K. Nexi, we combine Eqs 57 and 58 to obtain
K
E
((NN))) > H)
S 2cc x 2 2// /WIK
(59)
V NA (wk)t
24

---

Published in Transations on Machine Learning Research (07/2022
Further, we plug in Eqs.
53 and 59 in Eq.52
K
H
E
Σ
min
11,
S 22H1W/+2/2 IWIH H1 /max(1, Nu(wn,))
(60)
k=1
This concludes the proof.
Lemma 6. Let W be a finite set and Ps(0) == {p Vw E W, --lp(l//)) pe:(-w))l Be(w, be a [W]- reclangular confidence set over probabilily distributions p² (.lw) with m oulcomes, where (c(.)) is the empirical estimation of p" (.w)). Suppose at each time T, we observe an state wi w and sample from p" (./w). If
log
67 w 2m
Be(w,) 6) V max (1, (ww)) with Ne(w) Et=1 I(w, = w), then the true distributions p lie in the confidence set (6) with probability at least 1
8 2/8
Proof. We adapt the proof from Lemma 17 in Jaksch et al. (2010). We note that,
Pr(p" & Pc)
Pr
I1 (.1w) pel. [w)l Be 6)
WEW
17 [/W/mm
2 log [1p"(.1w) Dc( Bc(-1w)ll1 2
Σ Pr
max ( 1, [.(wW
we W
t7 1////20
(118)
2 log Pr [10(-| De(. -e((1w))li 2
max 11
WEW R=0
where (i) follows from the definition of the confidence set, i.e., the probability distributions do not lie in the
confidence set if there is at least one state in which ||p (- w) -(- w)ll 2 (e(w, 6), (ii) follows from the definition of (w,,, 8) and a union bound over all w E W and (iii) follows from a union bound over all possible values of (wr). To continue, we split the sum into n = O and n > 0:
2 log
ΣΣ Pr [p'(.|w) (.(lw))li 2 n=
max 11
t7 F1
2 log
Σ Pr
[-p((1w)) - - (1)ll)l 2
6
NEW n=1
if ===
+ Σ Pr -f((w)))(( 2
2log
8
WEW
('1W/2m41 8
log
Pr
(1*(-1w) f (w)ll 2
+ 0
WEW 11
(6)
8
1/W/2 exp
log
8
2
25

---

Published in Transations on Machine Learning Research (07/2022
/ 2218 2m for non-trivial cases. More
where (i) follows from the fact that (-<(-1))) - Pc( 1e(-1w)ll1 <
specifically,
8< 1,,,2
/ 2log
2lo0((522 2, Σ (1)(1) [E(m]
8
Ilp"(: (.Iw) - pc( [e/l/ll11- -
+ fr(il w)) 2;
(61)
and (ii) follows from the fact that, after observing n samples, the d'ddeiiatoon of the true distribution p from the empirical one & over m events is bounded by:
Pr -( p(1)11 e) S 2 exp -n 6²
(62)
Lemma 7. Consider the following minimization problem:
minimize
W
(63)
subject to 1=1
T1 b d, Σ 11
0 Vi E (1,...,.. m..
where d d 0, b; 2 0 Vi E (1, (1....,m)) m); E, by
and 0 S S u2 S Wm. Then, the solution to the above.
minimization problem is given by:
min (1, bi 3 ff=1
x
b;
ifi> 1 and Ei= 21 S
(64)
otherwise.
Proof. Suppose there is {a/; E; a = 1, x 2 0} such that E, < E, ui first index where x' # zj, then it's clear that 2 > 2z.
Let j E m.....mm be the
If = 1:
m
2 6,1=
b11
2 2
b.1
b
+ 1
6
>d
(65)
2
1=2
1=
If 1:
m
m - b >
d
m
d
Σ
br b-1=
by
2
b.
x
2
+
1
=
(66)
(=++1
Both cases contradict the condition Em |oc by S d.
Lemma 8. For the value function Vi defined in Eq. 10, we have that:
((... (s) +
Σ (als) (c((s,)++ + Σ (8,1)8,a) V (l, (67)
asA
s'ES
Proof.
Vs,,, d) 1 [(s,d)+ +
Ep(s',
p(s', Te (((, ds) Po. pl (s(sd))
26

---

Published in Transations on Machine Learning Research (07/2023
Σ (aldoao(aas)ce(ssse ce(m)(s,d) + (s) + ΣΣΣ aEA
p(s' 1s, a)pmasaa (als)) 1t1/s, tT(s, d))
s'ESaEA
(60) (r.edd)) d) E (alaeaaaaals) (c(s,,)+ Ep(s'ss,a) V (
(68)
aEA
3'E8
where (i) is the standard Bellman equation in the standard MDP defined with dynamics and costs 4, (ii)
follows by replacing and p with oquations and 4, and (iii) follows by car d) = ce(d") + ez (d' d).
Lemma 9, min a - b} & min a) + min(I for T,a.b20.
Proof. Assume that a < - a b. Then,
T a T a7, (T) if aabbsT T =Sa+T'=min[Tj"""
a
min(T, aT,
(69)
TT = + a+b= min([[a] + min if fasbsatbeT
if Tsasbsatb
27

---

Published in Transations on Machine Learning Research (07/2022)
C Implementation of UCRL2 in finite horizon setting
ALGORITHM 2: Modified UCRL2 algorithm for a finite horizon MDP M = (,,
Require: Cost C [c(s, a)], confidence parameter 8 (0,
1: ((Na(s, ))) (s, a, s'))) + INITIALIZECOUNT((
for L....KK K do
3: for s, 6 8,a E A do
a,(s,a,s')
4: if Ne(,,a) # 0 then fe(6'18, s,
else (s <- [3
Na(s,a)
14 22k 2(21122AA11))
5: Be(s,a,5)
max (1, N=(s,a))
6: end for
7: =² < BETENNEDDVALEEEETTATTOOOOOO.PP 8k. C)
50 INTTALLCONDPTIONSS)
9: for t 0,..., L.....,-a L do
Take action d, nł (st), and observe next state 8141-
11:
(s) &- (st, ar) + as, end for
(1 ai, 8441 +1
13:
14:
end
15: Return n
ALGORITHM 3: It implements EXTEANEDVALUUEIIRRAVIYY which is used in Algorithm Require: Empirical transition distribution p(-1s,a), cost c(s, a), and confidence interval B(8, a, 8). WATTAALzEVA.DEEUNeeTT
I: INITAALZZPPOICYO.,
2: n < S
3: -or=--11 To..
4: for 8 S do
for E do
6:
$i.....,,, S. + SORT(U441
# 0441 .... (0-1(()))
p(s() + min(1, ((sils, + ((a))
7:
8:
p(s.) p(s(ls, v1 in Itn n
9:
while EvES p($)) do
11:
p(s() = max ma 10,10111 E Es. p()))
1 1-11 end while (ss,a) c(s Ry (veti (8'))
13:
15: end for
vr(s) min A (g(s, a)}
17: T((s)= + arg min.c a}}
end
19:
end for
20: Return
28

---

Published in Transations on Machine Learning Research (07/2022)
D
Distribution of cell types and traffic levels in the lane driving environment
Table 1: Probability of cell types based on traffic level.
road
grass
stone
car
0.7
0.2
0.1
0
light
0.6
0.2
0.1
0.1
heavy 0.5
0.2
0.1
0.2
Table 2: Probability of traffic levels based on the previous row.
no-car
light
heavy
no-car
0.99
0.01
light
0.01
0.98
0.01
heavy
0
0.01
0.99
E
Performance of the human and machine agents in obstacle avoidance task
Total environment cost
x10
x10
10
2
0
Machine Human Optimal
Machine Human Optimal
Policy
Policy
(a) 70 no-car
(b) 70 (light,
Figure 8: Performance of the machine policy, human policy with oμ 2, and the optimal policy in terms of total cost. In panel (a), the episodes start with an initial traffic level no-car and, in panel (b), the episodes start with an initial traffic level To E (light, heavy).
F The amount of human control for different initial traffic levels
(3f = G
Human Control Rate
0.,, 0.2
0.4
no-car
light Initial Traffic Level
heavy
Figure 9: The amount of human control rate using UCRL2-MC switching algorithu for different initial traffic levels. For each traffic level, we sample 500 environment and average the human control rate over them. Higher traffic level results in more human control, as the human agent is more reliable in heavier traffic.
29

---

Published in Transations on Machine Learning Research (07 (07/2022)
2.0
1.00
Regret Ratio
Regret Ratio
0.75
1.5
0.50
1.0
0.25
16
2
3
4
5
6 7
8
9
10
Number of Actions
Number of Agents
(b)
Figure 10: Ratio of UCRL2-MC regret to UCRL2 for (a) set of action sizes and (b) different numbers of agents. By increasing the action space size, the performance of UCRL2-MC gets worse but remains within the same scale. addition, UCRL2-MC outperforms UCRL2 in environments with a larger number of agents.
G Additional Experiments
In this section, run additional experiments in the RiverSwim environment investigate the effect of action space size and the number of agents in team the total regret.
G.1 Action space size
To study the effect of action space size on the total regret, we artificially increase the number of actions by planning m steps ahead. More concretely, we consider new MDP, where each time step consists of steps of the original RiverSwim MDP, and the switching policy decides for all the steps at once. The number of actions in the new MDP increases to 2m while the state space remains unchanged. We consider setting with single team of two agents with p = 0 and p = 1, i.e., one agent always takes action right and the other takes left. We run the simulations for 20,000 episodes with m = {1, (1.2.....44 4], i.c., with the action size of 2, 4, 8, 16. Each experiment repeated for times. We compare the performance of our algorithm against UCRL2 in terms of total regret. Figure 10 (a) summarizes our results; The performance of UCRL2-MC gets worse by increasing the number of actions the regret bound directly depends the action size (Theorem 2). However, the regret ratio still remains within the same scale even after doubling the number of actions. One reason is that our algorithm only needs to learn the actions laken by the agents to find the optimal switching policy. If the agents' policies include a small subset of actions, our algorithms will maintain a small regret bound even in environments with huge action space. Therefore, we believe a more careful analysis can improve our regret bound by making it a function of agents' action space instead of the whole action size.
G.2 Number of agents
Here, our goal is to examine the impact the number of agents on the total regret achieved by our algorithm. To this end, we consider the original RiverSwim MDP (i.c., two actions) with a single team of agents, where we rum our simulations for n {3, 4. ..... .00. and 20,000 episodes for each n. We choose p, i.e,, the probability of taking action right for agents (0, (0.,--..... a=2,1). 1). As shown in Figure 10 (b), UCRL2-MC outperforms UCRL2 as the number of agents increases. This agrees with Theorem 2, derived regret bound mainly depends on the action space size [A), while the UCRL2 regret bound depends on the number of agents [D].
30


Reviews:
[{"review_id": "uVQHoyjFgW", "reviewer": "Reviewer_EUMX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nIn this work the authors studied an alternative form of MDP in which the RL agent only controls the switches between particular human/non-autonomous agents that controls the generation of \"low-level actions\", for which the RL agent cannot be modified by the RL agent. This may relate to a specific instance of hierarchical RL in which the switching policy controls the high-level, marco action where the low-level actions are generated by policies that in this work needs to be fixed and cannot be fine-tuned. In general making the action space of RL more structural and introducing more priors into simplifying the original problem-agnostic RL framework is an important direction to make RL more efficient. \n\nWeaknesses:\nThere are four questions that I hope the paper can address:\ni) I understand that in this work the authors specifically fixed the \"low-level\" policy and formulate the problem of RL as designing the high-level switching policy. In term of novelty, how does that compare with the option-RL framework which has been around in the community for long? Can any of the option terminology be used here?\nii) One difference (that I appreciate the authors' pointed out) between existing \"policy mixing\" approach with the proposed approach is planning upon realized actions generated by low-level agents, whereas in many existing approaches the high-level agent only plans to choose which low-level agent, but not on choosing the realized actions. This formulation is similar to the \"mixture-of-expert\" approach, for example mentioned in Section 6 of this paper: https://arxiv.org/abs/2206.00059. I agree that we should augment the state space with the realized actions (which corresponds to the P_D environment introduced in this work). However, one question I have is why should we keep track of the evolution of the policy indexes in the state and state transition of the MDP, on top of just keep track of the transition of realized actions via P_D? At the end different agents may generate identical actions but our system may not necessarily care which agents generate the these actions.  Is there a Bellman optimality condition to show that the augmented state space chosen by the authors is \"sufficient\" and \"necessary\"?\niii) In the UCRL algorithm (in say (7) or (11)), it seems the environment is also minimized (due to the optimistic MDP formulation of UCRL). But in this case, this is exactly like optimizing both high-level policy \\pi that generates macro actions and low-level policies that generate micro actions in hierarchical MDPs. Similar to most criticisms of these approaches in the literature (of options or hierarchical RL), how does the UCRL approach ensure that the training procedure does not degenerate into picking a flat, non-hierarchical policy?   \niv) The motivation of extending the algorithm to learning a policy to switch multiple teams of agents is unclear. Are the authors claiming this extension to be more data-efficient for the multi-task RL setting? If so, besides extending the UCRL bound, more analysis and studies in the multi-task problem formulation are needed. Otherwise, this section 5 seems like an incremental addition and may be a distraction of the main message. \nv) To better illustrate the effectiveness of the algorithms besides a simple grid-based driving experiment, it'd be good to see how this proposed algorithm performs in more involved numerical experiments. Also, even in the simple domain where the assumptions of the theorem can be verified, it'd be good to see if the numerical regret bound matches with the ones proven in the theoretical results, to understand the tightness of the theory bounds.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors proposed a MDP framework to study an RL problem that is less autonomous. In particular, they restrcit the problem formulation into one that allow allows the RL agent to take some of the actions and\nleave the remaining ones to human agents, and argue that the resulting performance may be better than the performance\nof the fully autonomous counterpart. To solve this problem defined by the authors, they extended the UCRL-based algorithm that uses upper confidence bounds on the agents’ policies and the environment’s transition probabilities to find a sequence of switching policies in a final horizon two-layer MDP. Same as standard UCRL-style analysis, the total regret of the derived algorithm  algorithm with respect to the optimal switching policy is sub-linear in the number of learning steps, and with multiple teams of agents operating in a similar environment, the proposed algorithm can also benefit from maintaining shared confidence bounds for the environments’\ntransition probabilities to have a better regret bound than traditional problem-agnostic MDP algorithms.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Main changes to improve the paper include addressing the aforementioned questions and making the motivation of this paper more compelling, in terms of i) comparing this approach with the option or option critic framework, ii) the rationale behind having P_D and P decomposed this way, especially on the reasons on instead of just using the realized actions for planning, what is the additional value to keep track of how the actual actions are generated by the particular controllers, iii) similar to the criticisms of options, when executing the proposed UCRL2-like algorithm, where both the switching policy pi and \"low-level policy\"  p_d are minimized (in say (7) or (11)), how can one avoid having all the policies degenerate into a single flat policy that is the same as solving the original MDP problem, iv) what is the main motivation of extending the original algorithm to switch across multiple teams of agents as in Sec 5? , v) more involved experiments besides a simple grid-based domain as a  proof-of-concept.  \n\nTherefore, at this point I'd not vote for acceptance of this paper until the above comments are addressed.", "broader_impact_concerns": "It's a paper focused on deriving new RL theories and algorithms on a specific two-layer MDP, in my opinions there are no particular ethical concerns.  ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LssDA1YhKQ", "reviewer": "Reviewer_CWXS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nMajority of work in the community is focused on proposing alogrithms or systems aiming for full autonomy in some way. However, for real world applications often human are required in the loop and one needs an ensemble of policies. Relatively less work has focused on this problem, so it's good to have this paper trying to formalize some aspects of such settings.\nThe paper is clearly laid out and well written. The choice of 2-layer MDP is well defended and is quite insightful in understanding the problem decomposition. While I am not the best judge for confirming whether the proof is correct, it does seem alright to me and given the framing choices, the improvements in regret bounds make sense. The simple experiments also have their setup quite clearly laid out with clear descriptions and help support the case for their effectiveness at least theoretically.\n\n## Weaknesses\n\nThe paper doesn't actually solve many important challenges for their solution to be of actual practical interest (especially for human policies mixed in). Concept of time, especially human reaction time is completely missing from the discussion, with Markovian policies assumed to be a decent abstraction. \nSimilarly while given the theoretical nature of majority of the work, some discussion of the general reward design principles in this setting is warranted.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on formalizing the problem of switching control policies between multiple agents in a team. A 2-layer MDP is used to frame this problem and an on-line learning algorithm with provable guarantees (UCRL2-MC) is proposed. The proposed algorithm uses upper confidence bounds on agent policies as well as environment transition probabilities. Shared confidence bounds allow better regret bound than problem agnostic algorithms. The improvements are demonstrated on a pair of toy problems.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The title is too broad and does not correctly characterize the contributions of the paper. A single paper obviously doesn't solve all the problems and baby steps are fine, but there are many ways to frame the problem of switching agent policies and 2-layer MDP choice in the paper is just one among many. \nThe current limitations of the work could be much better stated as noted above.\n\nGiven the interests laid out in future work, while the means are quite different, [1] might be of interest given the interaction of switching between policies specializing in different transition dynamics settings using ane estimate of transition dynamics information.\n\n[1] https://arxiv.org/abs/1903.01567", "broader_impact_concerns": "Not required.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HYlAKWlPB4", "reviewer": "Reviewer_8f5p", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n- (Relevance of the problem) The paper tackles the relevant problem of learning to switch between agents/policies online. This setting has important ramifications, especially the application in which human and artificial agents alternate control over a system;\n- (Formulation) The proposed formulation of the switching problem into a 2-layer MDP is neat, and it allows for independent estimates of the agents' policies and the transition dynamics;\n- (Clarity) The reported regret rates are easy to interpret, and they allow for a clear comparison with UCRL2 operating on a naive formulation of the switching problem into a 1-layer MDP;\n- (Numerical validation) The numerical validation is compelling, and it supports the main theoretical claims;\n- (Related Work) I am not particularly familiar with this area of research, but the related work section is well-written, and it seems to include the most relevant previous works (especially the lazy-MDP framework of Jacq et al., 2022).\n\n*Weaknesses*\n- (Regret rates) Unfortunately, handling the confidence sets independently for the agents' policies and the transition dynamics does not lead to a clear dominance in the regret rates over what one can achieve with standard UCRL. \n\t- In the single-team setting, the regret rate of UCRL-MC is at most on par with UCRL2, a conclusion that seems to be supported by the numerical experiments. However, the rate of UCRL-MC comes with its own drawbacks, such as a direct dependence with the cardinality of the action set A, which is instead avoided by UCRL2.\n\t- Instead, in the peculiar setting of multiple teams independently operating on similar environments, UCRL-MC seems to bring more clear benefits, especially if the number of such teams (N) is huge. While the reported experiment partially support this conclusion, the rates of UCRL2 and UCRL-MC still fall on a similar scale;\n- (Techniques) The analysis seems to be mostly incremental w.r.t. standard UCRL2, which suggests a limited independent interest for the employed techniques;\n- (Notation) The notation is a little convoluted, which makes it hard to follow some of the derivations.\n\n*General comment*\n\nThis seems to be a valuable and interesting paper overall, even if the regret rate in the single-team setting is somewhat disappointing. I believe the paper could do more to support the relevance of the multiple-teams setting, as it is the one where their approach provides most of the benefit, but it also less clear what are the potential applications. Anyway, I think that the 2-layer formulation of the switching problem, along with the multiple-confidence algorithmic approach, could be valuable as an intermediate step towards an even more relevant setting, which is the switching problem over learning agents. Thus, I think this paper might be worthy of publication with minor changes.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of learning to switch between a set of fixed (but unknown) policies in a sequential setting. First, it formulates the problem as a 2-layer MDP, in which one layer is devoted to the policy selection, the other to the action selection. Then, it proposes a variant of the UCRL2 algorithm that deals with multiple confidence sets simultaneously, one for the unknown transition dynamics (as in standard UCRL2) and the others for the unknown policies. A regret analysis for this newly introduced algorithm is carried out both in a setting where a single team of agent (policies) interact with the environment, and in a setting where multiple teams of agents operate independently on the same environment. Finally, the paper provides an experimental validation in an obstacle-avoidance illustrative domain.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- (Notation) The notation is not always easy to follow. I would suggest the authors to consider a more (visually) clear separation between the symbols that concern the switching-layer of the MDP, and the symbols that concern to the action-layer of the MDP. As a minor note, the paper is not always consistent in reporting the cardinality of the sets with the symbol $|\\cdot|$.\n- (Discussion of the setting) I would suggest the authors to include a deeper discussion on the relevance of the multiple-teams setting and its potential applications.\n- (Experiments) The reported regret analysis suggests that UCRL-MC may struggle in domains with huge actions sets. Thus, I would consider an illustrative experiment to debunk this possibility. It could be also interesting to include experiments with larger teams of agents.", "broader_impact_concerns": "I think that the paper does enough to address the potential impact concerns. On the one hand, this paper is mainly theoretical. Moreover, the authors clearly report (at the end of the introduction) that adopting their approach for real world tasks, especially including human-machine collaborations, should require further analysis of the practical aspects.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work formalizes the problem of learning to switch between a set of fixed control policies (agents) in a team, rather than going about solving a large policy space. A two-layer MDP is used to frame this problem, where one layer is for policy selection, and the other is to select actions. A learning algorithm with provable guarantees (UCRL2-MC) is proposed (a variant of UCRL2 algorithm), which uses upper confidence bounds on agent policies as well as environment transition probabilities. A regret analysis is carried out both in a setting where a single team of agents interact with the environment, and in a setting where multiple teams of agents operate independently in the same environment. They conduct a pair of experiments to demonstrate their approach.

Many issues were raised in the review period, during which the authors clarified the relationship of this work with existing frameworks (e.g. options) and methodologies (mixture-of-experts), which was raised by reviewer EUMX. The authors also better scoped claims and contributions (which helped address the issues raised by reviewer CWXS). Additional experiments (suggested by 8f5p) were conducted to investigate the effect of the action space size on the regret bound, and also to show benefits over existing approaches that they build on (e.g. UCRL2). Some were then noted in the main article (from the Appendix section) for clarity.

Reviewer EUMX mentions in the rebuttal discussion that several questions such as degeneration and distinction from existing work have been clarified, but the main issue they have with the work is that the experimental justification of this work is still on the weaker side. EUMX is not proposing a complex task, but one that is more related to the theory developed in the work to demonstrate clearly how the approach affects the performance in practice, resulting in a leaning reject recommendation from the

Other reviewers, such as CWXS, didn't mind the use of the 'toy problems' (quoted in their review) to demonstrate the improvements offered by (UCRL2-MC), since a main contribution is the theoretical guarantees that had been provided (which to some extent, offset the weaker set of experiments). Reviewer 8f5p initially had issues and concerns with the experiments too, but these were addressed during the rebuttal period, and reviewer CWXS was left satisfied with all of their concerns addressed.

While I agree with EUMX that the experiments are lacking when compared to many experimental papers (which are the majority of RL literature these days), and that the approach can be seen as incremental with modest novelty (which will likely lead to rejection at typical so called 'top' ML conferences), I also acknowledge that the contribution of this work also comes from the theoretical analysis, and that the other 2 reviewers were satisfied that the experiments (simple as they may be), were convincing enough to support the claims made (however modest they may be), and that they also complement the theoretical contributions. From the reviewers' comments, I also believe that there would at least be *some* individuals in TMLR's audience that would like to know the findings of this paper, so based on these points, my decision is to recommend **acceptance** of the work, as they satisfy TMLR's acceptance criteria:

---
The acceptance decision for a submission is based on the answers to the following questions:

1. Are the claims made in the submission supported by accurate, convincing and clear evidence?
2. Would at least some individuals in TMLR's audience be interested in knowing the findings of this paper?

Papers should be accepted if they meet the criteria, even if the contribution or significance of the work is modest.

---

That being said, I believe EUMX’s comments are still helpful, and their valuable feedback has helped shape and improve the work to its current acceptable level. I encourage the authors to extend their effort to include more practical examples as suggested, as that is still required to make this work broadly applicable beyond a niche research community.

Decision: Accept (poster)