Learning in Non-Cooperative Configurable Markov Decision Processes
Year: 2021

Abstract:
The Configurable Markov Decision Process framework includes two entities: a Reinforcement Learning agent and a configurator that can modify some environmental parameters to improve the agent’s performance. This presupposes that the two actors have identical reward functions. What if the configurator does not have the same intentions as the agent? This paper introduces the Non-Cooperative Configurable Markov Decision Process, a framework that allows modeling two (possibly different) reward functions for the configurator and the agent. Then, we consider an online learning problem, where the configurator has to find the best among a finite set of possible configurations. We propose two learning algorithms to minimize the configurator’s expected regret, which exploit the problem’s structure, depending on the agent’s feedback. While a naïve application of the UCB algorithm yields a regret that grows indefinitely over time, we show that our approach suffers only bounded regret. Furthermore, we empirically validate the performance of our algorithm in simulated domains.

text: The Configurable Markov Decision Process framework includes two entities: a Reinforcement Learning agent and a configurator that can modify some environmental parameters to improve the agent’s performance. This presupposes that the two actors have identical reward functions. What if the configurator does not have the same intentions as the agent? This paper introduces the Non-Cooperative Configurable Markov Decision Process, a framework that allows modeling two (possibly different) reward functions for the configurator and the agent. Then, we consider an online learning problem, where the configurator has to find the best among a finite set of possible configurations. We propose two learning algorithms to minimize the configurator’s expected regret, which exploit the problem’s structure, depending on the agent’s feedback. While a naïve application of the UCB algorithm yields a regret that grows indefinitely over time, we show that our approach suffers only bounded regret. Furthermore, we empirically validate the performance of our algorithm in simulated domains.

heading: 1 Introduction
text: The standard Reinforcement Learning [RL, 40] framework involves an agent whose objective is to maximize the reward collected during its interaction with the environment. However, there exist real-world scenarios in which the agent itself or an external supervisor (configurator) can partially modify the environment. In a car racing problem, for example, it is possible to modify the car setup to better suit the driver’s needs. Recently, the Configurable Markov Decision Processes [Conf-MDPs, 29] were introduced to model these scenarios and exploit the configuration opportunities. Solving a Conf-MDP consists of simultaneously optimizing a set of environmental parameters and the agent’s policy to reach the maximum expected return. In many scenarios, however, the configurator does not know the agent’s reward, and their intentions are different, leading to new forms of interaction between the two actors. For instance, imagine we are the owner of a supermarket, and we have to arrange the products on the shelves. Our objective is to increase the company’s final profit; on the other hand, a customer aims to spend the shortest time possible inside the supermarket and buy the indispensable products only. Since we do not know the customer reward function, the only possibility is to try different dispositions and observe the customers’ reactions. What if we knew what buyers
⇤ Work done when Giorgia Ramponi was at Politecnico di Milano.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
are most interested in? In this case, we can strategically decide how to position other products close to the popular ones to induce the customer in a more profitable behavior for the supermarket owner.
In this paper, we model these scenarios introducing the Non-Cooperative Markov Decision Processes (NConf-MDP). This novel framework handles the possibility of having different reward functions for the agent and the configurator. While Conf-MDP assumes that the configurator acts to help the agent to optimize its expected reward, an NConf-MDP, instead, allows modeling a wider set of situations, including the cases in which agent and configurator display a non-cooperative behavior. Obviously, this setting cannot be addressed with straightforward application of the algorithms designed for cooperative Conf-MDP. In fact, if the configurator and the agent optimize separately different objectives, they might not converge to an equilibrium strategy [52, 12, 51, 13]. In this novel setting, we consider an online learning problem, where the configurator has to select a configuration, within a finite set of possible configurations, in order to maximize its own return. This framework can be seen as a leader-follower game, in which the follower (the agent) is selfish and optimizes its own reward function, and the leader (the configurator) has to decide the best configuration, based on its reward. Clearly, to adapt its decisions, the configurator has to receive some form of feedback related to the agent’s behavior. We analyze two settings based on whether the configurator observes just the agent’s actions or, in addition, a noisy version of the agent’s reward.
Contributions In this paper, we extend the Configurable Markov Decision Process setting to deal with situations where the configurator and the agent have different reward functions. We call this new framework the Non-Cooperative Markov Decision Process (NConf-MDP, Section 3). Then, we formalize the problem of finding the best environment configuration, according to the configurator’s reward, as a leader-follower game, in which the agent (follower) reacts to each presented configuration with its best response policy (Section 4). We provide a first algorithm, Action-feedback Optimistic Configuration Learning (AfOCL), to tackle this problem under the assumption that the configurator observes the agent’s actions only (Section 5.1). We show AfOCL achieves finite expected regret, scaling linearly with the number of admissible configurations. As far as we know, this represents the first problem-dependent regret analysis in a Multi-Agent RL setting. Then, we introduce a second algorithm, Reward-feedback Optimistic Configuration Learning (RfOCL), that assumes the availability of a noisy version of the agent’s reward, in addition to the agent’s actions (Section 5.2). We prove that, under suitable conditions, RfOCL further exploits the structure underlying the decision process, removing the dependence on the number of configurations. The analysis use novel ideas, combining the suboptimality gaps of the configurator with those of the agent. Finally, we provide an experimental evaluation on benchmark domains, inspired by scenarios that motivate the NConf-MDPs framework (Section 7). The proofs of the results presented in the paper are reported in Appendix B. A preliminary version of this work was presented at “AAAI-21 Workshop on Reinforcement Learning in Games” [36].

heading: 2 Preliminaries
text: A finite-horizon Markov Decision Process [MDP, 35] is a tuple M = (S,A, p, µ, r,H) where S is a finite state space (S = |S|), A is a finite action space (A = |A|), p : S ⇥A⇥ S ! [0, 1] is the transition model, which defines the density p(s0|s, a) of state s0 2 S when taking action a 2 A in state s 2 S, µ : S ! [0, 1] is the initial state distribution, r : S ! [0, 1] is the reward function, and H 2 N 1 is the horizon. A stochastic decision rule ⇡h : S ⇥A ! [0, 1] with h 2 [H] prescribes the probability ⇡h(a|s) of playing action a 2 A in state s 2 S. A stochastic policy ⇡ = (⇡
1 , · · · ,⇡H) 2 ⇧H is a sequence of decision rules, where ⇧H is the set of stochastic policies over the horizon H . A finite-horizon Configurable Markov Decision Process [Conf-MDP, 29] is defined as CM = (S,A,P, µ, r,H) and extends the MDP considering a configuration space P instead a single transition model p. The Q-value of a policy ⇡ 2 ⇧H and configuration p 2 P is the expected sum of the rewards starting from (s, a) 2 S ⇥A at step h 2 [H]:
Q⇡,ph (s, a) = r(s) + Esh0⇠p,⇡
" HX
h0=h+1
r(sh0)|sh = s, ah = a # ,
denoting with Esh0⇠p,⇡ the expectation w.r.t. the state distribution induced by ⇡ and p at step h0. The value function is given by V ⇡,ph (s) = Ea⇠⇡h(·|s)[Q ⇡,p h (s, a)] and the expected return
is defined as V ⇡,p = Es⇠µ[V ⇡,p 1 (s)]. In a Conf-MDP the goal consists in finding a policy ⇡⇤ together with an environment configuration p⇤ so as to maximize the expected return, i.e., (⇡⇤, p⇤) 2 argmax⇡2⇧H ,p2P V ⇡,p .

heading: 3 Non-Cooperative Conf-MDPs
text: The definition of Conf-MDP allows modeling scenarios in which agent and configurator share the same objective, encoded in a single reward function r. In this section, we introduce an extension of this framework to account for the presence of a configurator having interests that might differ from those of the agent. Definition 3.1. A Non-Cooperative Configurable Markov Decision Process (NConf-MDP) is defined by a tuple NCM = (S,A,P, µ, rc, ro, H), where (S,A,P, µ,H) is a Conf-MDP without reward and rc, ro : S ! [0, 1] are the configurator and agent (opponent) reward functions, respectively. Given a policy ⇡ 2 ⇧H and a configuration p 2 P , for every (s, a) 2 S ⇥A and h 2 [H] we define the configurator and agent Q-values as:
Q⇡,pc,h (s, a) = rc(s) + Esh0⇠p,⇡
" HX
h0=h+1
rc(sh0)|sh = s, ah = a # ,
Q⇡,po,h(s, a) = ro(s) + Esh0⇠p,⇡
" HX
h0=h+1
ro(sh0)|sh = s, ah = a # .
We denote with V ⇡,pc,h (s) = Ea⇠⇡h(s)[Q ⇡,p c,h (s, a)] and V ⇡,p o,h = Ea⇠⇡h(s)[Q ⇡,p o,h(s, a)] the value functions and with V ⇡,pc = Es⇠µ[V ⇡,p c,1 (s)] and V ⇡,p o = Es⇠µ[V ⇡,p o,1 (s)] the expected returns for the configurator and the agent respectively.

heading: 4 Problem Formulation
text: While for classical Conf-MDPs [29, 27] a notion of optimality is straightforward as agent and configurator share the same objective, in an NConf-MDP, they can display possibly conflicting interests. We assume a sequential interaction between the configurator and the agent that resembles the leaderfollower protocol [10, 6, 34, 38]. First, the configurator (leader) selects an environment configuration p 2 P , where P is a finite set made of M stochastic transition models P = {p 1
, . . . , pM}. Then the agent (follower) plays a policy chosen by a best response function f : P ! ⇧H , such that: f(p) 2 argmax⇡2⇧H V ⇡,po . The solution concept that we use is the well-known Stackelberg equilibrium [43, 15, 30, 32, 19]. It captures the outcome in which the configurator’s transition model is optimal, under the assumption that the agent will always respond optimally [26]. However, this definition includes the possibility of ties, i.e., situations in which multiple agent optimal policies exist, with possibly different performance for the configurator. Therefore, it is necessary to employ a tie-breaking rule, i.e., a criterion to select one agent best response. Different tie-breaking rules lead to different Stackelberg equilibria, and the two prevailing solution concepts in the literature are the Strong Stackelberg Equilibrium (SSE) and the Weak Stackelberg Equilibrium (WSE). A policy-transition model pair (⇡⇤, p⇤) forms an SSE if ties are broken in favor of the configurator:
p⇤ 2 argmax p2P V f S (p),p c and ⇡ ⇤ := fS(p) 2 argmax ⇡2f(p) V ⇡,po .
The WSE can be constructed by breaking the ties against the configurator. In the rest of the paper, we employ the concept of SSE; however, every result can be applied to any deterministic tie-breaking rule. We call ⇡⇤p the application of the best response function f S
to a transition model p. Notice that the goal of the configurator is well-defined, whenever deciding the function fS . From an online learning perspective, this goal is to minimize the expected regret:
E[Regret(K)] = E  X
k2[K]
max p2P V ⇡p,pc V ⇡pk ,pkc . (1)
To lighten the notation, in the following, we will denote with ⇡i the agent’s best response policy to the configuration pi, i.e., ⇡⇤pi and with V i the configurator expected returned attained with configuration pi and policy ⇡i, i.e., V ⇡i,pic . Finally, we denote with V ⇤ = maxi2[M ] V i .
Agent’s Feedback The configurator knows its reward rc, but it does not know the agent reward ro. At each episode k 2 [K], the configurator selects a configuration pIk 2 P and observes a trajectory of H steps generated by the agent’s best response policy ⇡Ik . We study two types of feedback: • Action-feedback (Af). The configurator observes the states and the actions played by the agent (s
1 , a 1 , . . . , sH 1, aH 1, sH), where ah ⇠ ⇡Ik,h(sh). • Reward-feedback (Rf). The configurator observes the states, the actions played by the agent, and a
noisy feedback of the agent reward function (s 1 , er 1 , a 1 , . . . , sH 1, erH 1, aH 1, sH , erH), where ah ⇠ ⇡Ik,h(sh) and erh is sampled from a distribution with mean ro(s) and support [0, 1].2
The Rf models situations in which the agent’s reward is known under uncertainty, or it is obtained in an approximate way through Inverse Reinforcement Learning [33].
Connections with Bandit Algorithms The online problem that we are facing can be seen as a stochastic multi-armed bandit [25], in which the arms are configurations, and the configurator receives a random realization of its expected return at every episode. Thus, in principle, it can be solved by standard algorithms for bandit problems, such as UCB1 [1]. These algorithms are computationally less demanding than those we will present in the next sections. On the other hand, they suffer regret that grows logarithmically, i.e., indefinitely, with the number of episodes. Indeed, they do not exploit either the information regarding the agent’s policy or the structure induced by the agent’s reward function. We will prove that, instead, the proposed algorithms, which use the problem structure, suffer bounded regret. Furthermore, our algorithms are combined with UCB1 confidence intervals, so their regret, at finite time, is never worse than the one of UCB1.

heading: 5 Optimistic Configuration Learning
text: In this section, we present two algorithms for the online learning problem introduced in Section 4. The first algorithm uses only the collected agent decisions to optimistically learn the best configuration (Section 5.1). In the second algorithm, we also use the noisy reward feedback to construct an algorithm that leverages the structure that links together all the transition probability models: the agent’s reward function ro (Section 5.2). In Appendix C, we provide some hints about the adversarial case to illustrate the additional complexities that arise. In the adversarial setting, the agent can play a different policy at each step, inside the set of possible policies that satisfy the SSE.

heading: 5.1 Action-feedback Optimistic Configuration Learning
text: We start with the action-feedback (Af) setting, in which the configurator observes the agent’s actions only. The idea at the basis of the algorithm we propose, Action-feedback Optimistic Configuration Learning (AfOCL), is to maintain, for each configuration, a set of plausible policies that contains an agent’s best response policy. The configurator plays the transition model that maximizes an optimistic approximation of its value function. Specifically, for every i 2 [M ], k 2 [K], and h 2 [H] we denote with Aik,h(s) ✓ A the set of plausible actions in state s at step h for configuration pi at the beginning of episode k. For every model pi, the first time we visit an (s, h)-pair and observe the agent’s action a ⇠ ⇡i,h(·|s), we set Aik,h(s) = {a}. For the non-visited (s, h)-pairs, we leave Aik,h(s) = A. Based on this, we can compute an optimistic approximation
eV ik,h of the configurator value function V ih :
eV ik,h(s) = rc(s) + max a2Aik,h(s)
X s02S pi(s 0|s, a)eV ik,h+1(s0), (2)
and eV ik,H(s) = rc(s). eV ik,h can be computed applying a value-iteration-like algorithm [35] that employs the iterate as in Equation (2). 3 Clearly, if the agent is playing deterministically, it holds that Aik,h(s) = {⇡i,h(s)} for all visited (s, h)-pairs and, consequently, eV ik,h(s) V ih(s). Instead, if the agent is playing stochastically, we possibly observe different actions whenever visiting (s, h) and we record just the first one. The following lemma shows that even for stochastic agents, if the SSE tie-breaking rule is employed,
eV ik,h is optimistic. 2
Clearly, the results we present can be directly extended to subgaussian distributions on the reward.
3
Notice that the computational complexity decreases as the number of visited states increases and, in any case, is bounded by that of value iteration O HS2A . Therefore, the time complexity of AfOCL is O KMHS2A .
Algorithm 1 Action-feedback Optimistic Configuration Learning (AfOCL). 1: Input: S, A, H , P = {p
1 , . . . , pM} 2: Initialize Ai
1,h(s) = A for all s 2 S , h 2 [H], and i 2 [M ] 3: for episodes 1, 2, . . . ,K do 4: Compute
eV i,UCBk for all i 2 [M ] 5: Compute
eV ik for all i 2 [M ] 6: Play pIk with Ik 2 argmaxi2[M ] min{eV ik , eV UCBk } 7: Observe (sk,1, ak,1, . . . , sk,H 1, ak,H 1, sk,H) 8: Compute the plausible actions for all s 2 S and h 2 [H]:
Aik+1,h(s) = ( {ak,h} if i = Ik and s = sk,h and Nk,h(s) = 0 Aik,h(s) otherwise
9: end for
Lemma 5.1. The value function eV ik,h(s) computed as in Equation (2) is such that eV ik,h(s) V ih(s) for all s 2 S , h 2 [H], and i 2 [M ]. In addition, we compute the confidence interval for UCB1 looking at the transition models as arms: eV i,UCBk = ¯V ik +H p 2 log k/Ni,k, where ¯V ik is the sample mean of the observed return for model pi and Ni,k is the number of times the algorithm plays model i up to episode k. Thus, at each episode k 2 [K] the configurator plays the transition model pIk maximizing the optimistic approximation:
Ik 2 argmax i2[M ] min{eV ik , eV i,UCBk }.
The pseudocode of AfOCL is reported in Algorithm 1.
Regret Guarantees We now provide an expected regret bound for the AfOCL algorithm. If the agent’s policy ⇡i is deterministic, it is not hard to get convinced that AfOCL suffers bounded regret since whenever an (s, h)-pair is visited under a pi, the agent reveals its (deterministic) policy ⇡i. Thus, either an (s, h)-pair is visited with high probability, or it will impact only marginally on the performance. The main challenge arises when the agent is playing a stochastic policy ⇡i for some pi. AfOCL just memorizes the first observed action for each (s, h), pretending the agent’s policy to be deterministic. Let b⇡i be the policy that plays the action memorized by AfOCL at the end of the K episodes, filled with the true agent’s policy for the non-visited (s, h)-pairs. By construction, the support of b⇡i is contained into the support of the true agent’s policy ⇡i. Clearly, if ⇡i is optimal for the agent reward, b⇡i is too. Furthermore, since the agent and the configurator are playing an SSE, b⇡i will lead to the same configurator’s performance as ⇡i. Indeed, if this were not the case, there would exist another deterministic policy optimal for the agent, leading to higher performance for the configurator, contradicting the definition of SSE. The following result shows that by switching ⇡i with b⇡i changes the regret just by a multiplicative factor depending on the mismatch between the visitation distributions induced by the two policies, di,h and bdi,h respectively. Theorem 5.1 (Regret of AfOCL). Let NCM = (S,A,P, µ, rc, ro, H) with P = {p1, . . . , pM} be the M configurations. The expected regret of AfOCL at every episode K > 0 is bounded by:
E[Regret(K)]  O min ( H2
X
i2[M ]: i>0
log(K)
i
| {z } UCB1 regret
, MH3S2⇢
| {z } AfOCL regret
)! , (3)
where ⇢ is the maxi2[M ]: i>0 E h maxs2S maxh2[H] bdi,h(s) di,h(s) i .
The result might be surprising as the regret is constant and independent of the suboptimality gaps between the configurations, i.e., i = V ⇤ V i for every i 2 [M ]. As supported by intuition, we need to spend more time discarding MDPs that are more similar in performance to the optimal one. Formally, the maximum number of times a suboptimal configuration pi is played is proportional to 1/ i (and not proportional to 1/ 2i as in standard bandits). This is because we just need one visit to
every reachable state. We underline that the term ⇢ , which indicates the expected ratio between the estimated policy’s induced states distribution and real policy’s induced states distribution, is equal to 1 when the agent plays a deterministic policy and bounded by SH in the worst case (see Lemma B.3). As far as we know, Theorem 5.1 is the first problem-dependent result for regret minimization for a multi-entity MDP. More details on the proof are given in the Appendix B.

heading: 5.2 Reward-feedback Optimistic Configuration Learning
text: The main drawback of AfOCL is that every transition model is treated separately, preventing from employing the underlying structure of the environment, which is represented by the agent reward function ro. Indeed, if the configurator knew ro, it could find the optimal configuration with no need for interaction by simply computing an agent’s best response policies for the SSE. The algorithm we propose in this section, Reward-feedback Optimistic Configuration Learning (RfOCL), employs the reward feedback (Rf), i.e., at every interaction, the configurator can see also a noisy version of the agent’s reward function. The crucial point is that ro is the same regardless of the chosen configuration, and, for this reason, it provides a link between them. Specifically, for every k 2 [K] and s 2 S, RfOCL maintains a confidence interval for the agent reward function Rk(s) = [ro,k(s), ro,k(s)] obtained using the samples collected up to episode k 1 regardless of the played configuration. We apply Höeffding’s inequality to build the confidence interval: bro,k(s)± q
log(2SHk2) max{Nk(s),1} , where Nk(s) is the number of visits of state s in the first k 1 episodes,
and bro,k(s) is the sample mean of the observed rewards for state s up to episode k. Given the estimated reward, for every configuration i 2 [M ], we can compute a confidence interval for the agent’s Q-values Qk,h(s, a) = [Qio,k,h(s, a), Q i o,k,h(s, a)], by simply applying the Bellman equation:
Qi o,k,h (s, a) = ro,k(s) + X
s02S pi(s
0|s, a)max a02A Qi o,k,h+1 (s0, a0),
Q i o,k,h(s, a) = ro,k(s) +
X s02S pi(s 0|s, a)max a02A Q i o,k,h+1(s 0, a0),
and Qi o,k,H (s, a) = ro,k(s) and Q i o,k,H(s, a) = ro,k(s). If the true reward function belongs to the confidence interval, i.e., ro 2 Rk, then the true Q-value belongs to the corresponding confidence interval, i.e., Qih 2 Qk,h. Consequently, we can use Qk,h to restrict the set of plausible actions in a state without actually observing the agent playing the action in that state. Indeed, the plausible actions are those that have a Q-value upper bound larger than the maximum Q-value lower bound:
eAik,h(s) = ⇢ a 2 A : Qio,k,h(s, a) max
a02A Qi o,k,h (s, a0) . (4)
In other words, if the upper Q-value of an action is smaller than the largest lower Q-value, it cannot be the greedy action, and it is discarded. Clearly, if we observe, for the first time, the agent playing an action in (s, h) at episode k we can reduce the plausible actions to the singleton ak,h, as in the action-feedback setting (Section 5.1). Based on this refined definition of plausible actions, we can
compute the optimistic estimate eV ik,h of the configurator value function V ih as in Equation (2) and proceed playing the optimistic configuration.
The pseudocode of RfOCL is reported in Algorithm 2. It is worth noting that we need to keep track of the states that have been already visited because for those, we know the agent’s action, and there is no need to apply Equation (4). This is why we introduce the counts Nk,h(s)4.
Regret Guarantees We now give a regret bound for the RfOCL algorithm. Obviously, the same arguments for AfOCL can also be applied for this extended version, and then the regret bound of Theorem 5.1 is valid for RfOCL. Moreover, for this algorithm, we prove that the regret, under the following assumption, does not depend on the number of configurations. Assumption 1. There exists ✏ > 0 such that: mini2[M ] mins2S maxh2[H] dih(s) ✏, where dih(s) is the probability of visiting the state s 2 S at time h 2 [H] in configuration pi under the agent’s best response policy ⇡i.
4
The value iteration dominates the computational complexity of an individual iteration of RfOCL (steps 5
and 9), leading, as for AfOCL, to O KMHS2A .
Algorithm 2 Reward-feedback Optimistic Configuration Learning (RfOCL) 1: Input: S, A, H , P = {p
1 , . . . , pM} 2: Initialize Ai
1,h(s) = A for all s 2 S , h 2 [H], and i 2 [M ] 3: Initialize ro,1(s) = 1, ro,1(s) = 0, and N1,h(s) = 0 for all s 2 S and h 2 [H] 4: for episodes 1, 2, . . . ,K do 5: Compute
eV i,UCBk for all i 2 [M ] 6: Compute
eV ik for all i 2 [M ] 7: Play pIk with Ik 2 argmaxi2[M ] min{eV ik , eV UCBk } 8: Observe (sk,1, erk,1, ak,1, . . . , sk,H 1, erk,H 1, ak,H 1, sk,H , erk,H) 9: Compute ro,k+1(s), ro,k+1(s), and Nk+1,h(s) for all s 2 S and h 2 [H] using erk,1 · · · erk,H
10: Compute Qi o,k+1,h (s, a) and Q i o,k+1,h(s, a) for all s 2 S , a 2 A, h 2 [H], and i 2 [M ] 11: Compute the plausible actions for all s 2 S and h 2 [H]:
Aik+1,h(s) =
8 > <
> : {ak,h} if i = Ik and s = sk,h and Nk,h(s) = 0 Aik,h(s) if Nk,h(s) > 0 eAik+1,h(s) otherwise
with eAik+1,h(s) as in Equation (4). 12: end for
This assumption requires that in every model pi 2 P the agent has non-zero probability, in some step h, to visit every state s. This allows shrinking the confidence intervals for the reward of every state to estimate the agent’s policy correctly, regardless of the played configuration. Notice that this assumption is less strict than requiring the well-known ergodicity of the Markov process induced by any policy, used in many algorithms [9, 21, 44].5 Under Assumption 1 we prove the following regret guarantee. Theorem 5.2 (Regret of RfOCL). Let NCM = (S,A,P, µ, rc, ro, H) with P = {p1, . . . , pM} be the M configurations. Under Assumption 1, the expected regret of RfOCL at every episode K > 0 is bounded by:
E[Regret(K)]  O min ( H2
X
i2[M ]: i>0
log(K)
i
| {z } UCB1 regret
, MH3S2⇢
| {z } AfOCL regret
, K + ⇡2
3
| {z } RfOCL regret
)! ,
where ⇢ is defined as in Theorem 5.1, K is the smallest integer solution of the inequality K 1 +✓ 2H2S2 log(2SHK 2 )
2 2 Q
+ q K 1 2 log(SHK 2 ) ◆ 1 ✏ , = maxi2[M ] i, i.e., the maximum suboptimality
gap, and Q is the minimum positive gap of the agent’s Q-values (see Appendix B).
The regret bound removes the dependence on the number of models M , as K is clearly independent of M , but it introduces, as expected, a dependence on the minimum visitation probability ✏. The proof of the result is reported in Appendix B. Since RfOCL exploits additional information compared to AfOCL and the set of plausible actions Aik,h of RfOCL are subsets of those of AfOCL, the regret bound AfOCL (Theorem 5.1) also holds for RfOCL. Thus, we can take as regret bound for RfOCL the minimum between K + ⇡ 2
3 and MH3S2. We underline that, as far as we know, this is the first proof that takes into consideration the sub-optimality gap of the uncontrollable entity, the agent, and the sub-optimality gap of the controllable entity, the configurator. This permits to derive a problem dependent regret bound. We think that similar techniques can also be of interest for Markov games.

heading: 6 Related Works
text: The idea of altering the environment dynamics to improve the agent’s learning experience has been exploited before the introduction of Conf-MDPs. Curriculum learning [8] provides the agent with 5
Moreover, the configurator can force this assumption since it has the control over the environmental transition model.
a sequence of environments, of increasing difficulty, to shape the learning process with possible benefits on the learning speed [e.g., 14, 16]. Although the learning process is carried out in a different environment, the configuration is typically performed in simulation only. The setting more similar to Non-Conf-MDP is the one presented in [47], where the configurator and the agent have opposite reward functions (similar to a zero-sum game). In the Conf-MDP framework, instead, the configuration opportunities are an intrinsic property of the environment [29]. The initial approaches entitled the agent of the configuration activity and, consequently, this task was totally auxiliary to its learning experience [29, 39, 27]. More recently, it has been observed that environment configuration can be actuated even by an external entity, opening new opportunities for the application of environment configurability, including settings in which the configurator’s interest conflicts with those of the agent. For instance, in [28] the configurator acts on the environment to induce the agent to reveal its capabilities in terms of perception and actuation. Instead, in [17] a threatener entity can change the transition probabilities either in a stochastic or adversarial manner. More generally, environment configuration carried out by an external entity has been studied in the field of planning as a form of environment design [48]. Thus, our NConfMDP unifies these settings, allowing for arbitrary agent’s and configurator’s reward functions. An interesting connection is established with the robust control literature [31, 20]. Whenever the two reward functions are opposite, i.e., the interaction between the agent and the configuration is fully competitive, the resulting equilibrium corresponds to a robust policy. Indeed, while the agent tries to maximize its expected return, the configurator places the agent in the worst possible environment. Configurable environments (cooperative and non-cooperative) share similarities with environment design [49]. At a high level, the two frameworks share analogous objectives: they both aim at determining an environment with a certain goal that can differ from that of the agent. However, there are some notable differences. In particular, the classical environment design formulation [49] assumes that the configurator (called “interested party”) knows the agent’s best response function, while in our approach, we learn it by interaction. Nevertheless, the general environment design makes no assumption about the underlying environment, that might not me an MDP. Instead, [22] limit to MDPs and considers a form of cooperative environment design in which the goal is to maximize the agent’s performance. Interestingly, some works [22, 37] also account for a cost function to penalize expensive environment configurations.
The design of our approaches is based on the OFU principle used for stochastic multi-armed bandits [e.g., 23, 1, 18, 25] and MDPs [e.g., 2, 7, 3]. Moreover, our learning setting with reward feedback is related to structured bandits or bandits with correlated arms. 6 Interestingly, for certain structures, it is known that bounded regret is achievable [11, 24], a property that is enjoyed by both our algorithms. Our setting is also close to the Stochastic Games model, in which two or more agents act in an MDP to maximize their own reward functions. Recently, the stochastic game’s framework gains growing interest [5, 4, 50], especially in the offline setting i.e., we can control all the agents. For this reason, these approaches do not apply to our setting, where we have the control of the configurator only.
6
In our case, playing a single configuration provides information about the opponent’s reward, which, in turn,
provides information about the value of all configurations.
Although some works tackle the online setting [44, 45, 41], where we can control only one agent, all of these algorithms work in the zero-sum setting only.

heading: 7 Experiments
text: In this section, we provide the experimental evaluation of our algorithms in two different settings: when the policies are stochastic and when the policies are deterministic. For these experiments, we provide two novel environments: Configurable Gridworld and the Student-Teacher. We compare the algorithms with the standard (theoretical) implementation of UCB1 [1]. The environment description and additional results can be found in Appendix D.
Stochastic policies The Configurable Gridworld is a configurable version of a classic 3⇥ 3 Gridworld. The agent’s starting state is in the cell (0, 1), and its goal is to minimize the number of steps required to reach the exit located in the cell (2, 1). The configurator takes reward 1 when the agent occupies the central cell (1, 1) and 0 otherwise. In a classic Gridworld, the optimal policy would be trivial, as the agent would proceed straight to the exit. In this Configurable Gridworld, instead, the configurator can set the “power” p of a stochastic obstacle located in the cell (1, 1). When the agent is in that cell and performs action “go right” to reach the exit, it will hit the obstacle, and will remain in the same position with probability p. The configurator’s goal is to tune this probability to keep the agent in the central cell for the maximum number of steps. The M configurations differ in the probability p and are obtained by a regular discretization of [0, 1]. In the first experiment (Figure 1), we considered 10 and 30 configurations with a number of episodes K = 2000 and K = 4000 and horizon H = 10. For this experiment, the agent plays optimal stochastic policies. We can see that AfOCL and RfOCL suffer constant regret, whereas UCB1 displays a logarithmic regret, as expected. Specifically, RfOCL outperforms AfOCL and stops playing suboptimal configuration in less than 500 episodes in both cases. This can be explained because, being Assumption 1 fulfilled (in fact, the agent has the probability 0.1 of failing its action), RfOCL is able to exploit the underlying structure of the problem more effectively.
Non-Ergodicity In Figure 2, we have only three configurations designed to induce an optimal agent’s policy that generates a non-ergodic Markov chain. In this case, the optimal policies are deterministic, and we violate Assumption 1. For this reason, we observe that AfOCL and RfOCL display very similar behavior but still significantly better than UCB1.
Deterministic policies: Student-Teacher The Student-Teacher environment models a simple interaction between a student and a teacher. There is a set of exercises, with a different level of teacher hardness and student hardness each. The teacher has to decide the optimal sequence of exercises in order to make the student acquire as much knowledge as possible. The student’s goal is to maximize the number of exercises and to reduce the hardness of the proposed exercises. At each timestep, the student decides whether to answer the exercise or not. If it answers, it receives a reward equal to the level of “correctness” of the exercise, the teacher receives a reward corresponding to the level of exercise’s “teacher hardness”, and they end up to the next exercise. If the student does not
answer, the student and the teacher will receive 1, and with a probability of 0.7, the next exercise will be easier to solve. In Figure 3, the results with M 2 {40, 60, 100} and horizon H = 10 are shown. The configurations represent the distribution over the next exercise, given a positive answer. In every run, we change the student hardness of the exercises. We observe that both AfOCL and RfOCL suffer significantly less regret compared to UCB1 and tend to converge to constant regret as expected. It is interesting to observe that, in line with our analysis, the gap between AfOCL and RfOCL appears more evident as the number of configurations grows.

heading: 8 Conclusions
text: In this paper, we have introduced an extension of the Conf-MDP framework to account for possible non-cooperative interaction between the agent and the configurator. We focused on an online learning problem in this new setting, proposing two regret minimization algorithms for identifying the best environment configuration within a finite set, based on the principle of optimism in the face of uncertainty. We proved that even when the agent’s policy is stochastic, and the configurator observes the agent’s actions, it is possible to achieve finite regret that depends linearly on the admissible number configurations. Furthermore, we illustrated that we can remove this dependence if the configurator observes a possibly noisy version of the agent’s reward and under sufficient regularity conditions on the environment. This paper also gives interesting insights on the importance of properly exploiting the available feedback to construct efficient algorithms. Moreover, as far as we know, the ones we have presented are the first problem-dependent regret results for multi-entity MDPs. The experimental evaluation showed that our algorithms display a convergence speed significantly faster than UCB1, and RfOCL tends to outperform AfOCL thanks to the exploitation of the additional structure. Future research directions include a deeper analysis of the adversarial setting, as well as the application to inverse reinforcement learning.
Limitations and Societal Impact
Methods that incentive the manipulation of users’ behavior can have, generally speaking, a negative societal impact, when used, for instance, in a marketing campaign. Nevertheless, our work is mainly theoretical and, at the present level, can hardly be used in a malevolent way. Another relevant aspect is the cost of environment configuration. We are aware that reconfiguring the environment is an activity that typically leads to higher costs compared with policy learning. However, we did not consider this aspect in the formalization of the Non-Cooperative Conf-MDP since it would possibly make the problem more complex (like, for instance, when considering bandits with switching costs).

Review summaries:
The authors provide an algorithm for online learning in a non-cooperative configurable MDP. They propose a setting where a configurator can choose a transition model for the MDP from a finite set of models. The goal is then to observe the agent's behaviour (either the state-action sequences or a noisy reward) and to learn an optimal configuration that results in maximum configurator reward given that the agent behaves optimally with respect to its own reward function.  

This paper presents an extension of the existing Configurable-MDP framework to a non-cooperative setting; one where the agent and the configurator could also have different reward functions. This setting (referred to as Non-cooperative Configurable MDPs) allows for modelling a wider range of situations, which also include the scenario where the agent and configurator display non-cooperative behaviour. The problem-setting is modelled as a leader-follower game, with the configurator as the leader and the agent as the follower. The authors present two algorithms for the configurator: AfOCL- which assumes that during online interaction the configurator can observe the agent's actions; RfOCL- which assumes that during online interaction the configurator can observe the agent's actions and obtains noisy estimates of its reward as well. The authors go on to prove that AfOCL achieves finite expected regret, which scales *linearly* with the number of possible configurations. This is already an improvement over the standard UCB algorithm which yields a regret that grows indefinitely over time. They also show that RfOCL the regret does not depend on the number of configurations under the assumption that the agent has a non-zero probability in some time-step of the horizon to visit every state in the MDP. The experimental evaluations were carried out on two environments: A configurable gridworld, and a simulated teacher-student environment. In both settings, their algorithms obtain constant  cumulative regret, as opposed to the logarithmic regret suffered by the UCB algorithm, validating their result.

The paper studies learning in configurable MDPs with two-agents, a reinforcement learning agent and a configurator that can modify the environment parameters. In contrast to prior work, the paper considers a setting in which the configurator and the agent can have misaligned objectives. The setting is formally modeled as a Stackelberg game, in which the configurator is the leader that  selects a transition model and the agent is the follower that plays the best response policy under this model. The goal is to design a learning algorithm for the leader with provable regret guarantees. The paper provides two learning algorithms for the configurator and formally analyzes their regret properties, which turn out to be better than those of a naive solution based on UCB1. The paper supports its theoretical claims using simulation-based experiments.  

This paper proposes an extension to the configurable MDP framework, which implicitly assumes a shared reward function by the acting agent and the configurator, to the non-cooperative case where the reward functions of the two agents may be different and unknown to the other. Modeling the problem as a leader follower game, the papers present two online regret-minimization algorithms based on a multi-armed bandit strategy to learn the best environment configuration under different conditions. In the first, the configurator has access only to observed state-action traces (AfOCL), and in the second the configurator additionally observes noisy reward signals (RfOCL). The core idea of the algorithms is to iteratively prune the space of "plausible policies" of the acting agent based on observed feedback to compute an increasingly accurate optimistic value function for each environmental configuration for the configurator at the start of each episode. The authors prove that both algorithms incur finite expected regret, and show that regret scales linearly in the number of configurations for AfOCL, and is independent of the number of configurations in the case of RfOCL. Finally, the authors provide empirical results of the performance of AfOCL and RfOCL against the baseline UCB1 in two experimental domains, a gridworld domain and a teacher-student domain.