Learning in Non-Cooperative Configurable Markov Decision Processes
Authors: Giorgia Ramponi
Alberto Maria Metelli
Alessandro Concetti
Marcello Restelli
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Configurable MDP
Multi-agent learning

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 the same 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 setting that allows having 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 exploits the problem's structure, depending on the agent's feedback. While a naive 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 show the performance of our algorithm in simulated domains.


Learning in Non-Cooperative Configurable Markov Decision Processes
Giorgia Ramponi"
Alberto Maria Metelli Politecnico di Milano Milan, Italy al beerromaria..mmtllllppo.....
ETH AI Center Zurich, Switzerland gramponi ietpoon@@ethzz.c. ch
Alessandro Concetti Politecnico di Milano
Marcello Restelli
Politecnico di Milano
Milan, Italy
Milan, Italy
al cot.//roo..ooottttiiimcmmm... wtt.:mmaaal..lmmmmmmmm.m... polimi.
marcello.restellig 1mmiiii..m......mmm iimolmmmmi....
Abstract
The Configurable Markov Decision Process framework includes two entities: a Reinforcement Learning agent and a configurator that can modify some environ- mental parameters to improve the agent's 's performance. This presupposes that the two actors have identical reward functions. What the configurator does not have the same intentions the agent? This paper introduces the Non -oo-erooee Configurable Markov Decision Process, 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 find the best among finite set of possible configurations. We propose two learning algo- rithms to minimize the configurator's expected regret, which exploit the problem's ss structure, depending 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 our algorithm in simulated domains.
the agent's 's feedback. While naīve application of the
Introduction
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 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 model these scenarios and exploit the configuration opportunities. Solving Conf-MDP consists of simultaneously optimizing a set of environmental parameters and the agent's policy reach the maximum expected return. many scenarios, however, the configurator does not know the agent's '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 supermarket, and we have to arrange the products on the shelves. Our objective is to increase the company's 's final profit; on the other hand, 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 try different dispositions and observe the customers' reactions. What we knew what buyers
Work done when Giorgia Ramponi was at Politecnico di Milano.
35th Conference on Neural Information Processing Systems (NcurIPS 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-MDPP). 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-MDDI 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, order to maximize its own return. This framework can seen as leader-fold followrf 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 s behavior. We analyze two settings based on whether the configurator observes just the agent's s actions or, in addition, noisy version of the agent's '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-Coopen con-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 leader-follower game, in which the agent (follower) reacts each presented configuration with its best response policy (Section 4). We provide first algorithm, 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 introduce
Optimistic
the first problem-dependent regret analysis in Multi-Agent RL setting. Then, second algorithm, Reward-feede feedback Optimistic Configuration Learning (RfOCL), that assumes the availability of a noisy version of the agent's reward, in addition the agent's 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].
2 Preliminaries
A finite-horizon Markov Decision Process (MDP, 35] is a tuple M = A,,A,,, H) where S is a finite state space (S = =SS). AA is a finite action space (A = [A), p Axx + [o. is the transition model, which defines the density p(s'ls,a) a) of state s' E S when taking action
a E A in state s E S, μ. S + [0, 1] is the initial state distribution, r SS + [0, 1] is the reward function, and H E N>1 is the horizon. A stochastic decision rule na S x A
[0, with h E [H]
prescribes the probability Th (a|s) of playing action a E A in state 8 E S. A stochastic policy
(T) ( , ) IT is sequence of decision rules, where II is the set of stochastic policies over the horizon H.
A finite-horizon Configurable Markov Decision Process [Conf-MDP, 29] is defined as CMM AS,,, P,H,T, r, H) and extends the MDP considering a configuration space P instead a single transition model p. The Q-value of policy E II" and configuration p P is the expected sum of the rewards starting from (s, a) E S x A at step h E [H]:
H
Q7 (s,a) =
E Surn
Σ
r(sw)
s/. = = s.
denoting with Eay the expectation w.r.t. the state distribution induced by and p at step h'. The value function is given by :TT:(() Ea "s, a)] and the expected return

---

is defined as V = ( In Conf-MDP the goal consists in finding policy n together with an environment configuration p" so as maximize the expected return, i.c., (T p E arg x pep Va..
3 Non-Cooperative Conf-MDPs
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 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, P, pl, Tey Yox H), where (S, A, P, μ. H) is Conf-MDD without reward and Ter To S [0, 1] are the configurator and agent (opponent) reward functions, respectively.
Given policy II and configuration p P, for every (s,a) E x A and h [H] we define the configurator and agent Q-values as:
(5, a) = re(s) + E Sprpppe
ro(sw)]sh = 5, = a W'=h+1
Σ
(o a) =r((s)
E Spmpp
ro(sw))ss 8, LM=++1
Σ
We denote with V c. (s) Eaway()) (e)
(o) (2 (s, a)) and VoT. (s) Q. (s, (s,a) a)] the value func-
tions and with Va = Es
[V (s)) and VTT.P = E the expected returns for the
configurator and the agent respectively.
4 Problem Formulation
While for classical Conf-MDPs [29, 27] a notion optimality straightforward as agent and config- urator 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 leader- follower protocol [10, 6, 34, 38). First, the configurator (leader) selects an environment configuration p E P. where P is a finite set made of M stochastic transition models P {pI,.... pw): Then the agent (follower) plays policy chosen by a best response function f P - " such that: f()) arg , V.... iP. The solution concept that we use is the well-known Stackelberg equi- librium [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, is necessary to employ tie- rie-breaking rule, i.e., criterion to select one agent best response. Different tie- tie-breaking rules lead to different Stackelberg equilibria, and the two prevailing solution concepts in the literature the Strong Stackelberg Equilibrium (SSE) and the Weak Slackelbery Equilibrium (WSH). A policy-transition model pair (x²,'" ,,"" forms an SSE if ties are broken in favor of the configurator:
pd E arg max V (p).pp and n PEP
(p) E arg max V...P. nEf(p)
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 n the application of the best response function I 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 Regrett [K) = E Σ max VTP.P
Vo- TT PP
(1)
PEP
kE[K]
To lighten the notation, in the following, we will denote with ,, the agent's best response policy the configuration pi, i.c., Tp, and with / the configurator expected returned attained with configuration p. and policy Ta. i.c., V...P. Finally, we denote with V max VS.
3

---

Agent's Feedback The configurator knows its reward re. but it does not know the agent reward ro- At each episode & [K]. the configurator selects a configuration pt, E P and observes trajectory of H steps generated by the agent's is best response policy -,,- We study two types of feedback:
Action-feedhack (Af). The configurator observes the states and the actions played by the agent ($1, $i,41,...,,5p - -1 where ag A
Reward-feedback (Rf). The configurator observes the states, the actions played by the agent, and noisy feedback of the agent reward function (31, Fi, al...... - -1 -1, SH, THH) where aj 12 (5%. and i'y sampled from a distribution with mean (s) and support [0, 1].2
The Rf models situations in which the agent's 's reward is known under uncertainty, or 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 its expected return at every episode. Thus, in principle, it can be solved by standard algorithms for bandit problems, such UCBI [1]. These algorithms less demanding than those we will present in the next sections. On the other hand, they suffer regret that grows logarithmically, i.c., 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 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 of UCB1.
computationally
5 Optimistic Configuration Learning
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 '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 different policy at each step, inside the set of possible policies that satisfy the SSE.
5.1 Action-feedback Optimistic Configuration Learning
We start with the action-feedback (Af) setting. in which the configurator observes the agent's 's actions only. The idea at the basis of the algorithm we propose, Action-feedback Optimistic Configuration Learning (AfOCL), is maintain, for each configuration, set of plausible policies that contains an agent's 's best response policy. The configurator plays the transition model that maximizes an optimistic approximation of its value function. Specifically, for every E [M]. k E [K] and h E [H] we denote with A (s) C A the set of plausible actions in state at step h for configuration p; at the beginning of episode k. For every model pt. the first time we visit an (s, --prrir and observe the agent's action R Tei (-Is), we set Ai, (s) {a). For the non-visited (s, -ppari,s, we leave (s) A. Based
on this, compute an optimistic approximation V of the configurator value function Vy:
(s) = rs())+ + max Σ pi(s'ls, a) ( aEAi,, SEES
and (+) = rc(s.. V2 can be computed applying a value-iteration-lik algorithm [35] that employs the iterate as in Equation (2). Clearly, if the agent is playing deterministically, it holds that (s) = (s) for all visited (s, h)-pairs and, consequently. (s) 2 Vi))). 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 is optimistic.
tie-breaking rule is employed, V k.
CClearyy, the results we present can be directly extended to subgaussian distributions on the reward. 'Notice that the computational complexity decreases as the number of visited states increases and, in any case. bounded by that of value iteration O (HS²² A). Therefore, the time complexity of AfOCL is O M HS2 A).

---

Algorithm Action-feedback Optimistic Configuration Learning (AfOCL).
1: Input: A. H P {pr (pi....,PMM
2: Initialize Ai,n(s) = A for all E S, h e [H), and e [M]
for episodes .......: .. do
4: Compute V/L for all [M]
5: Compute Vi for all [M]
6: Play Pi, with Is arg m min V2, 1/CB)
7: Observe (sk.1, Og.1,.... 88. OR.HI 8k.1r)
8:
Compute the plausible actions for all E S and h [H]
(ann) (k))(s)
ifi and SE,6 and N&) =0
(k)
otherwise
9: end for
Lemma 5.1. The value function V2 (s) computed as in Equation (2) is such that (s) 2 (s) for all 8 E S, h E [H). and i E [M].
In addition, we compute the confidence interval for UCBI looking at the transition models as arms: V. V-L.CCB = V + H 2og k/N,,. where V is the sample mean of the observed return for model p; and Nr.: is the number of times the algorithm plays model up episode k. Thus, each episode E [K] the configurator plays the transition model pr, maximizing the optimistic approximation:
J arg max min Vg, TALUCB)
sE[M]
The pseudocode of AfOCL is reported in Algorithm
Regret Guarantees We provide expected regret bound for the AfOCL algorithm. If the agent's policy n; is deterministic, it is not hard to get convinced that AfOCL suffers bounded regret since whenever
(s, hi-ppirr is visited under Pi. the agent reveals its (deterministic) policy ma- Thus, either an (s, h) h)-pair is visited with high probability, or it will impact only marginally on the performance. The main challenge arises when the agent playing a stochastic policy for some p;- AfOCL. just memorizes the first observed action for each (s, h). pretending the agent's policy to be deterministic. Let n. be the policy that plays the action memorized by AfOCL the end of the K episodes. filled with the true agent's policy for the non-visited (s, -parris.. By construction, the support of म. is contained into the support of the agent's policy _;- Clearly, if x; is optimal for the agent reward, म. is too. Furthermore, since the agent and the configurator are playing an SSE, n will lead to the same configurator's 's performance 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 Ta with π, changes the regret just by multiplicative factor depending on the mismatch between the visitation distributions induced by the two policies, d',, and di respectively.
Ti Indeed, if this were the case, there
Theorem 5.1 (Regret of AfOCL), Let = (S, A, P. P.p,Ter Te, To, H) with P = (pI.....PPi Par} be the M configurations. The expected regret of AfOCL at every episode K bounded by:
log(K) A,
MH 1)
E[Regrer(K))] S s min
H²
Σ
(3)
:E[M]]A,>>0
UCBI regret
regret
( (x)
where p the max.e[M)-A,00 E max.sS maN
The result might be surprising as the regret is constant and independent of the suboptimality gaps between the configurations, i.e., A, V* Vi for every E [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 times suboptimal configuration p; is played is proportional to 1/A, (and not proportional to 1/2, in standard bandits). This is because just need one visit to
5

---

every reachable state. We underline that the term p, which indicates the expected ratio between the estimated policy's ss induced states distribution and real policy's 's induced states distribution, is equal to 1 when the agent plays deterministic policy and bounded by SH in the worst case (see Lemma B.3). As far as we know, Theorem 5.1 the first toolem-deeendeet result for regret minimization for multi-entity MDP. More details on the proof are given in the Appendix B.
5.2 Reward-feedback Optimistic Configuration Learning
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 re, it could find the optimal configuration with no need for interaction by simply computing an agent's 's best response policies for the SSE.
The algorithm we propose in this section, Reward-feedback Optimistic Configuration Learning (RIOCL), employs the reward feedback (Rf, i.e., at every interaction, the configurator can see also noisy version of the agent's reward function. The crucial point is that To is the same regardless of the chosen configuration, and, for this reason, it provides a link between them. Specifically, for every & [K] and E S, RfOCL maintains confidence interval for the agent reward function (s) = Ir, (s), [s)] obtained using the samples collected up to episode ht - 1 regardless of the played configuration. We apply Höeffding's 's inequality to build the confidence interval:
(s) =
log(2SHk*) where N₂ (s) is the number of visits of state in the first k 1 episodes, (ax(()
and (s. is the sample mean of the observed rewards for state s up to episode k. Given the estimated reward, for every configuration
[M], we can compute a confidence interval for the agent's Q-values Qx,n(s, a) = =Q (s, Qo,k, (s) by simply applying the Bellman equation:
2a (8) a) = [ra +
Σ Pr(s'1s, (s, a) max Q', O'
a'EA C. (s',a)),
s'ES
Co, a) = =To((s)+ +
Pi(s'1s, a) max C Σ
a'EAA (o,,,41((',
x'ES
and (',,, = ra,e =(a and Q Ro, (s, = (s). If the true reward function belongs to the confidence interval, i.c., To E RR, then the true Q-value belongs to the corresponding confidence interval, i.e., Qi E QR,h- Consequently, we can use QR, 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 Q- Q-value upper bound larger than the maximum Q-value lower bound:
A: {a a A: Co..n(s,)) 2 max Q' (s, a'EAA
(s -
(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 & we can reduce the plausible actions to the singleton dg.b, as in the action-feedback setting (Section 5.1). Based on this refined definition of plausible actions, we can compute the optimistic estimate Vi, of the configurator value function Vi as in Equation (2) and proceed playing the optimistic configuration.
The pseudocode of RIOCL is reported in Algorithm It worth noting that we need to keep track of the states that have been already visited because for those, we know the agent's is action, and there is no need to apply Equation (4). This is why we introduce the counts (s)+.
Regret Guarantees We now give a regret bound for the RIOCL 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 e > 0 such that: minje[M] minses maжне[и[ di (s) 2 E, where di (s) is the probability of visiting the state s E at time h E [H] in configuration p; under the agent's 's best response policy ni
'The value iteration dominates the computational complexity of an individual iteration of RIOCL (steps 5 and 9), leading, for AtOCL, to O M MSS A).

---

Algorithm 2 Reward-feedback Optimistic Configuration Learning (RFOCL)
1: Input: S, H {pi.....,PP .PM)
2: Initialize Ai,x(s) = A for E E, h E [H] and e [M]
Initialize (s) = 1, 1. = 0, and (s) for all & and & [M]
4: for episodes 1, 1.2....: K do
5: Compute V/c 171.CD for i [M]
Compute Vg for all [M]
Play Pl, with E arg mag min (72 1/
8: Observe (8K,1, FR.1, 08.11 18, -.. u1. u, Fk,ar)
Compute Fo, (5), Fo,441 and (s) for all E S and E [H] using Pk,1 Fk
10: Compute Q L0, (s, a) and Q0,441,a a) for all E S, a E A. [H], and i [M]
11:
Compute the plausible actions for all 8 S and h [H]:
[ak,A] (ia
if I and s sn,a and (s)
A (1) =
if Na, >
AE+La(()
otherwise
with A as in Equation (4).
12: end for
This assumption requires that in every model p; 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 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]. Under Assumption we prove the following regret guarantee.
Theorem 5.2 (Regret of RIOCL). Lei NCM = (e, To: H) with P {pI,.... Pas) be the M configurations. Under Assumption 1, the expected regret of RfOCL every episode K > 0 is bounded by:
log( K)
x² })
E Regret(()) K)) So min H² Σ
MHSS KA
A
:E|M]
UCBI regret
AfOCL regret
RJOCL regret
where p is defined in Theorem 5.1. K is the smallest integer solution of the inequality K 2 1
2H² 1og(2SHK")
V log(SHK²) A max4e[aa] A,, i.e., the maximum suboptimality
24/2
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, dependence on the minimum visitation probability c. The proof of the result is reported in Appendix B. Since RfOCL exploits additional information compared to AfOCL and the set of plausible actions A 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 A 3 and 52 We underline that, far 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 derive problem dependent regret bound. We think that similar techniques can also be interest for Markov games.
know, this is the first
Related Works
The idea of altering the environment dynamics improve the agent's learning experience has been exploited before the introduction of Conf-MDPs. Curriculum learning [8] provides the agent with
Moreover, the configurator can force this assumption since it has the control over the environmental transition model.
7

---

M
M
30
2000
150
Cumalative regret
600
Cumulative negret
1500
100
400
1000
200
500
50
0
1000 Round
2000
2000 Round
4000
500
1000
Epiioude
UCBI
AFOCL
HY B
RIOCL
UCBI-cuned
AFOCL
RIOCL
Figure 2: Cumulative regret for the Gridworld experiment without ergod- icity. 50 runs, 98% c.i.
Figure/ I: Cumulative regret for the Gridworld experiment. 50 runs, 98% c.i.
a sequence of environments, of increasing difficulty, to shape the learning process with possible benefits the learning speed [e.g.. s.. 14. 16). Although the learning process is carried out in 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-MDD framework, instead, the configuration opportunities are 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, 27J. 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 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 form of environment design [48]. Thus, our NConf- MDP unifies these settings, allowing for arbitrary agent's and configurator's 's reward functions. An interesting connection is established with the robust control literature [31, 20J. Whenever the two reward functions opposite, i.e., the interaction between the agent and the configuration is fully competitive, the resulting equilibrium corresponds to 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 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 's best response function, while in our approach, we learn 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 form of cooperative environment design in which the goal is to maximize the agent's 's performance. Interestingly, some works [22, 37] also account for cost function to penalize expensive environment configurations.
The design of our approaches is based on the OFU principle used for stochastic multi-armed ban- dits [e.g., 23, 1, 18, 25] and MDPs [e.g.. 2, 7, 3). Moreover, our learning setting with reward feedback related to structured bandits or bandits with correlated arms. 6 Interestingly, for certain structures, known that bounded regret is achievable [11, 24], 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 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.
'In our case, playing single configuration provides information about the opponent's 's reward, which, in turn. provides information about the value of all configurations.
8

---

40
M 60
100
4000
4000
4000
Cumulative regret
3000
3000
3000
2000
2000
2000
1000
1000
1000
4000
2000
4000
2000
4000
Episode
Episode
Episode
UCBI
AFOCL
RIOCL
Figure 3: Cumulative regret function of the episodes for the Teacher experiment. 50 runs, 98% c.i.
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.
7 Experiments
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- Student-Teacher. We compare the algorithms with the standard (theoretical) implementation UCBI 1 [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 Grid- world. The agent's starting state is in the cell (0. 1), and its goal 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 otherwise. trivial, as the agent would proceed straight to the exit. In this Configurable Gridworld, instead, the configurator can set the "power" p of 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.
classic Gridworld, the optimal policy would be
The M configurations differ 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 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 UCBI displays a logarithmic regret, as expected. Specifically, RIOCL outperforms AIOCL and stops playing suboptimal configuration in less than 500 episodes in both cases. This can be explained because, being Assumption fulfilled (in fact, 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 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, observe that AIOCL and RIOCL display very similar behavior but still significantly better than UCBI.
Deterministic policies: Student-Teacher The Student-Teacher environment models simple interaction between a student and a teacher. There is a set of exercises, with different level of teacher hardness and student hardness each. The teacher has decide the optimal sequence of exercises in order to make the student acquire as much knowledge possible. The student's goal is to maximize the number of exercises and reduce the hardness timestep, the student decides whether to answer the exercise or not. If it answers, it receives reward equal the level of "correctness" of the exercise, the teacher receives a reward corresponding the level of exercise's "teacher hardness", and they end up to the next exercise. If the student does not
proposed exercises. At each

---

answer, the student and the teacher will receive 11, and with a probability of 0.7, the next exercise will be easier to solve. In Figure 3. the results with M {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 RIOCL appears more evident the number of configurations grows.
8
Conclusions
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 's policy is stochastic, and the configurator observes the agent's 's actions, it possible 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 UCBI, 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 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 the formalization of the Non- Non-Cooperattiv Conf-MDD since would possibly make the problem more complex (like, for instance, when considering bandits with switching costs).
References
[1] Peter Auer, Nicolò Desa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(233):235 256, 2002.
[2] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems 2/ (NIPS), pages 89-96, Curran Associates, Inc., 2008
[3] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Mach. Learn., 91(3):325 349, 2013.
[4] Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 551-560. PMLR, 2020.
[5] Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[6] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC), pages 61-78. ACM, 2015.
10

---

[7] Peter L. Bartlett and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating mdps. Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), pages 35-42. AUAT Press, 2009.
[8] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML), volume 382 of ACM International Conference Proceeding Series, pages 41 41-8.. ACM, 2009.
[9] Ronen Brafman and Moshe Tennenholtz. R-MAX- A general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213-2333 2002.
[10] Michele Breton, Abderrahmane Alj, and Alain Haurie. Sequential stackelberg equilibria in two-person games. Journal of Optimization Theory and Applications, 59(1): 9-7 1988.
[11] Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet. Bounded regret in stochastic multi- armed bandits. In The 26th Annual Conference on Learning Theory (COLT). volume 30 of JMLR Workshop and Conference Proceedings, pages 122 134. JMLR.org. 2013.
[12] Lucian Busoniu, Robert Babuska, and Bart De Schutter. Multi-agent reinforcement learning:
A survey. In Ninth International Conference Control, Automation, Robotics and Vision, ICARCV 2006, Singapore, 5-8 December 2006, Proceedings, pages 1-6. IEEE, 2006.
[13] Benjamin Chasnov, Lillian J. Ratifff, Eric Mazumdar, and Samuel Burden. Convergence analysis of gradient-based learning in continuous games. In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Research, pages 935-9999 1444. AUAI Press, 2019.
[14] Kamil Andrzej Ciosek and Shimon Whiteson. OFFER: off-environment reinforcement learning. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1819-18255
AAAI Press, 2017.
[15] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings 7th ACM Conference on Electronic Commerce (EC), pages 82-90, ACM, 2006.
[16] Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In 1st Annual Conference on Robot Learning (CoRL), volume 78 of Proceedings of Machine Learning Research, pages 482-495. PMLR, 2017.
[17] Víctor Gallego, Roi Naveiro, and David Ríos Insua. Reinforcement learning under threats. In The Thirty-Third AAAI Conference Artificial Intelligence, pages 9939-99440 AAAI Press, 2019.
[18] Aurélien Garivier and Olivier Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In The 24th Annual Conference on Learning Theory (COLT), volume 19 of JMLR Proceedings, pages 359-376. JMLR.org, 2011.
[19] Qingyu Guo, Jiarui Gan, Fei Fang. Long Tran-Thanh, Milind Tambe, and Bo An. On the inducibility of stackelberg equilibrium for security games. In The Thirty-Third AAAI Conference on Artificial Intelligence, pages 2020-2028. AAAI Press, 2019.
[20] Garud N. Iyengar. Robust dynamic programming. Math. Oper. Res., 30(2):257-280, 2005.
[21] Michael J. Kearns and Satinder P. Singh. Ncar-optimal reinforcement learning in polynomial time. Mach. Learn., 49(2-3):209-233 2002.
[22] Sarah Keren, Luis Enrique Pineda, Avigdor Gal, Erez Karpas, and Shlomo Zilberstein. Equi- reward utility maximizing design in stochastic environments. In Proceedings of the Twenty-Sixh International Joint Conference on Artificial Intelligence (IJCAI), pages 4353-4360. ijcai.org, 2017.
[23] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985.

---

[24] Tor Lattimore and Rémi Munos. Bounded regret for finite-armed structured bandits. In Advances in Neural Information Processing Systems 27 (NIPS), pages 550-558, 2014.
[25] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020,
[26] George Leitmann. On generalized stackelberg strategies. Journal of optimization theory and applications, 26(4):637-644, 1978.
[27] Alberto Maria Metelli, Emanuele Ghelfi, and Marcello Restelli. Reinforcement learning in configurable continuous environments. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 4546-4555, PMLR, 2019.
[28] Alberto Maria Metelli, Guglielmo Manneschi, and Marcello Restelli. Policy space identification in configurable environments. Mach. Learn., 2021.
[29] Alberto Maria Metelli, Mirco Mutti, and Marcello Restelli. Configurable Markov decision processes. In Proceedings of the 35th International Conference Machine Learning, (ICML), volume 80 of Proceedings of Machine Learning Research, pages 3488-3497, PMLR, 2018.
[30] Thanh Hong Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe. Analyzing the effectiveness of adversary modeling in security games. In Proceedings of the Twenty-Sevnnth AAAI Conference on Artificial Intelligence. AAAI Press, 2013.
[31] Arnab Nilim and Laurent El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Advances in Neural Information Processing Systems 16 (NIPS), pages 839-846 MIT Press, 2003.
[32] Steven Okamoto, Noam Hazon, and Katia P. Sycara. Solving non-zero multiagent network flow security games with attack costs. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 879 888. IFAAMAS, 2012.
[33] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J. Andrew Bagnell, Pieter Abbeel, and Jan Peters. An algorithmic perspective on imitation learning. Found. Trends Robotics, 7(1-2):1-179, 2018.
[34] Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In The Thirty-Third AAAI Conference on Artificial Intelligence, pages 2149-2156. AAAI Press, 2019.
[35] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1994.
[36] Giorgia Ramponi, Alberto Maria Metelli, Alessandro Concetti, and Marcello Restelli. Online learning in non-cooperative configurable Markov decision process. AAAI-21 Workshop on Reinforcement Learning in Games, 2021.
[37] Sandhya Saisubramanian and Shlomo Zilberstein. Mitigating negative side effects via environ- ment shaping. In 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages (640-1642, ACM, 2021.
[38] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause, Learning to play sequential games versus unknown opponents. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[39] Rui Silva, Francisco S. Melo, and Manuela Veloso. What the world were different? gradient- based exploration for new optimal policies. In 4th Global Conference on Artificial Intelligence (GCAI), volume 55 of EPiC Series in Computing, pages 229-242. EasyChair, 2018.
[40] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[41] Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Provably efficient online agnostic learning in Markoy games. CoRR, 155/2010.150200 2020.
12

---

[42] Andrea Tirinzoni, Riccardo Poiani, and Marcello Restelli. Sequential transfer in reinforcement learning with a generative model. Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 9481-9492. PMLR, 2020.
[43] Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science Business Media, 2010.
[44] Chen- Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems 30 (NIPS), pages 4987-4997, 2017.
[45] Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory (COLT), volume 125 of Proceedings of Machine Learning Research, pages 3674 3682. PMLR, 2020.
[46] Andrea Zanette, Mykel J. Kochenderfer, and Emma Brunskill. Almost horizon-free structure- aware best policy identification with generative model. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 5626-5635. 2019.
[47] Haifeng Zhang, Jun Wang, Zhiming Zhou, Weinan Zhang, Yin Wen, Yong Yu, and Wenxin Li. Learning design games: Strategic environments in reinforcement learning. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI), pages 3068 3074. ijcai.org, 2018
[48] Haoqi Zhang, Yiling Chen, and David C. Parkes. A general approach environment design with one agent. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI). pages 2002-2014, 2009.
[49] Haoqi Zhang, Yiling Chen, and David C. Parkes. general approach environment design with one agent. In Proceedings of the s International Joint Conference Artificial Intelligence (IJCAI), pages 2002-2014, 2009.
[50] Kaiqing Zhang, Sham M. Kakade, Tamer Basar, and Lin F. Yang. Model-based multi-agent agent RL in zero-sum Markov games with near-optimal sample complexity. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[51] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. CoRR, 0ts/1911.1063. 2019.
[52] Martin Zinkevich, Amy Greenwald, and Michael L. Littman. Cyelic equilibria Markov games.
In Advances in Neural Information Processing Systems 18 (NIPS), pages 1641-1648, 2005.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The paper
mostly theoretical contribution and we think will not have any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] The assump- tions are all given in the main paper.
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen- tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See figures.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
27


Reviews:
[{"review_id": "kHT8RVBZdCf", "reviewer": "Reviewer_zQVR", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I enjoyed reading this paper and I find its results interesting and relevant. On the other hand, some aspects of the paper could be improved, e.g., in terms of clarity, and additional justification for the modeling assumptions could be provided. More detailed comments are below. \n\nNovelty: The paper studies a novel problem setting, building on the work of [29,27]. The setting has a clear motivation and the paper provides a good overview of the related work.  That said, the setting seems to be similar to adversarial attacks. How does this work relate to adversarial attacks in RL (e.g., adversarial attacks on policies 'Huang et al. Adversarial attacks on neural network policies', policy poisoning attacks 'Ma et al., Policy poisoning in batch reinforcement learning and control', attacks on environment parameters (rewards/transitions) 'Rakhsha et al., Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning', etc.)? \n\nQuality: In my opinion, the results of this paper advance the work on configurable environments, and the reasoning behind them is clearly explained. However, there are a few points that could be discussed in more detail: \n- The setting of the paper restricts the leader (configurator) to choose from a finite set of transition models. I think the implications of this restriction are not clearly stated in the text. For example, would the hardness result of Letchford et al. 'Computing Optimal Strategies to Commit to in Stochastic Games' apply in a more general case that doesn't place this restriction?  \n- In general, the setting is closely related to stochastic games. This connection is mentioned and partly discussed in Section 6, but it could be extended. For example, can we model this setting as a Stackelberg stochastic game (e.g., where the leader has an influence on transitions via its policy)? The paper highlights that it is the first to provide problem-dependent regret bounds in multi-agent RL. On the flip side, the setting of this paper seems more restrictive than stochastic games, which is a standard framework for multi-agent RL.   \n- Some of the variable/factors in the regret bounds could be more thoroughly explained. For example, it seems that the values of $\\rho$ in Eq. (3) or $\\hat K$ can be quite large, which could make the corresponding factors in the regret bounds bounds 'impractical'. Some discussion on this would be useful.   \n\nClarity: The structure of the paper is good, but some parts could be improved in terms of clarity as they contain typos or are ambiguous. Some notable examples include:\n- The equation in line 158, should $\\mathcal A_{i}^{k,h}(s)$ be a set of actions containing $\\pi(s)$? \n- The sentence in lines 188-187, why is the regret bound in (3) independent of \\Delta_i?\n- The sentence in lines 283-284, how does offline setting relate to controlling all of the agents?  \n\nSignificance: The paper provides two new learning algorithms for a configurable MDP setting and derives non-trivial regret bounds for them. These results are potentially relevant for other sub-areas of RL, including environment design and multi-agent RL. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The checklist states that the limitations are addressed in Section 8 (conclusion), but the conclusion only summarizes the paper and provides one sentence description of a future work. Since this is a theory paper, a discussion about limitations could explain the limitations of the modeling assumptions. Potential negative societal impacts are also not discussed, but given the topic of the paper, I don't find this necessary. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4/5 hours"}, "extra_text": {}}, {"review_id": "eMh9BpHk8R", "reviewer": "Reviewer_Qthd", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Primary Contributions:\n\n(1) Formal extension of the Conf-MDP model to the non-cooperative case (NConf-MDP). \n\n(2) Formalization of the problem as a leader follower game under Stackelberg equilibrium criteria. \n\n(3) Two online regret-minimization algorithms, AfOCL and RfOCL.\n\n(4) Proofs of bounded expected regret for both algorithms, the first linear in the number of configurations, the second independent of that.\n\n(5) Experimental evaluations on two domains, a gridworld domain and a student-teacher domain, against the baseline UCB1.\n\nPros:\n\n(1) Configurable MDPs are a recent addition to the community and well-motivated by many real-world problems. The non-cooperative setting considered in this paper is the natural extension of this framework and of interest to the community. \n\n(2) The overall structure was clear and the main ideas were well-explained.\n\n(3) The algorithms presented in the paper are simple and easily understood, but are intelligent in their approach and use of existing insights in related areas of multi-armed bandits and stackelberg games.\n\n(4) The authors provide rigorous theoretical guarantees on their algorithms, and the simulated results appear to match these results for the most part. \n\n(5) The algorithms perform well and significantly outperform the baseline, UCB1, in the experimental domains considered.\n\nCons:\n\n(1) Discussion of certain areas in the related work is lacking. In particular, the paper would benefit from a more detailed discussion of [45] and the broader area of environment design/shaping as it is central to the problem considered in the paper. We suggest some additional related work:\n\n --- \"Equi-Reward Utility Maximizing Design in Stochastic Environments.\" Keren et al. IJCAI 2017\n\n --- \"Mitigating Negative Side Effects via Environment Shaping.\" Saisubramanian and Zilberstein. AAMAS 2021. \n\n(2) Page 5, paragraph on \"Regret Guarantees\". The authors claim that \"either an (s, h) pair is visited with high probability, or it will impact only marginally on the performance\". Something is unclear, or perhaps incorrect, about this statement. A deterministic policy in a stochastic domain could to impactful states being visited infrequently. For instance, a state (say at timestep 1), with a small probability of being reached but with an arbitrarily high negative reward (e.g. a dead-end). Perhaps there is room for clarification.\n\n(3) Experiments are performed on very simple and small domains that are not entirely convincing.\n\nAdditional Comments:\n\n- In figure 1, should \"round\" be \"episode\"?\n\n- Is there any intuition to the term \\overline{K} in Theorem 5.2? As presented, it is hard to interpret the RfOCL regret in a meaningful way. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work assumes that the act of reconfiguring the environment does not have a cost to either configurator or acting agent. As the motivating domains are real-world problems with humans, if the environment is reconfigured dozens or hundreds of time for a single acting agent, possibly diminishing the cumulative reward earned by the agent in some configurations, this assumption may be violated. This assumption is also made in regular Conf-MDPs, but is perhaps more critical in the non-cooperative case where the reconfigurations are not always benefiting the human. Perhaps the authors could touch on this more. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Os-Zqkjv20S", "reviewer": "Reviewer_bBaH", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written clearly. However, some of the notation and concepts can be a bit dense and a use of a toy example or two can greatly help readability of the paper. Additionally, I feel the problem is not sufficiently motivated. The examples provided in the introduction are all well studied applications with numerous approaches. The authors do not do enough to explain why their new approach is necessary compared to past work. \n\nAs noted by the authors, the work in this paper is really similar to the multi-armed bandit formulation. However, the authors argue that in most bandit formulations, the regret is unbounded as they do not incorporate the agent's observed policy or reward into the algorithm as is done in this paper. While this is true, I don't know if the novelty in this paper is sufficient for a publication. As far as I can tell the approach is a relatively straightforward extension of using the observed actions or rewards of the agent to estimate the value function and choosing the corresponding best configuration. \n\nOverall, if the authors clarify the above point, I think the paper is interesting, and I believe has an incremental contribution to the literature. However, I believe it is not sufficiently well motivated and the contribution is not yet strong enough for publication. \n\nResponse: I appreciate the authors' response and they addressed my issues with the multi-armed bandit and novelty. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is mainly theoretical in nature and is unlikely to have an immediate social impact. However, the authors do provide some examples (such as a supermarket owner optimizing their shelves for profit) in which their work may be applied. It would be worth a small discussion to address if these applications for the work in this paper is actually a negative impact. For example, following on with the example provided in the introduction, is it a social good that we provide more methods for businesses to manipulate user behaviour to optimize their profits? Can this work be used in social network applications to increase user engagement by showing extremist or misleading content even if it is not the users' original intent? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "MJJCz98K6uc", "reviewer": "Reviewer_LFno", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros**\n\n* The paper was very clearly written and all the terminology well explained before they were presented.\n* The experimental setup was very clean, and the results presented provided insights into the workings of the 2 proposed algorithms. The fact that both stochastic and deterministic policies of the agent were considered, validates the performance of the algorithms in all settings.\n* The claim in the paper is that the regret bounds presented are the first problem-dependent regret results for multi-entity MDPs. This result can be exploited in the multi-agent adversarial RL setting to design more robust policies.\n\n**Cons**\n\n* Experimental Evaluations: The evaluation on the 2 environments presents proof of concept necessary to validate the theoretical results. However, it would be interesting to empirically see the performance of the algorithms on a purely adversarial setting, and get some further insights into worst-case performance in such a setting. Maybe illustration of the algorithms on such a setting could be an interesting add-on.\n\n**General Comments** Overall, the paper was well structured and the ideas were coherent. \n\n*Originality*: Novel\n\n*Clarity*: Clear\n\n*Quality*: Good\n\n*Significance*: High\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper explicitly states its limitations. As the paper mainly has theoretical results, it potentially has no negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers are fairly positive on this paper, which offers a novel take on the “environment design” problem in the non-cooperative (but not full adversarial) Stackelberg-type setting, using the framework of configurable MDPs. This new formulation is rather interesting, the (problem-dependent) regret analysis and the empirical confirmation offered are also valuable (though the empirical setup is critiqued as rather simple). The author response alleviated some of the reviewers questions and concerns, especially with regard to the problem formulation and its motivation There reviewers make some useful suggestions for improving the clarity of the paper, and related work suggestions. These should be addressed by the authors in revision. 

Decision: Accept (Poster)