A unified view of configurable Markov Decision Processes: Solution concepts,value functions,and operators

Abstract

In this paper, we provide a unified presentation of the Configurable Markov Decision Process (Conf-MDP) framework. A Conf-MDP is an extension of the traditional Markov Decision Process (MDP) that models the possibility to configure some environmental parameters. This configuration activity can be carried out by the learning agent itself or by an external configurator. We introduce a general definition of Conf-MDP, then we particularize it for the cooperative setting, where the configuration is fully functional to the agent’s goals, and non-cooperative setting, in which agent and configurator might have different interests. For both settings, we propose suitable solution concepts. Furthermore, we illustrate how to extend the traditional value functions for MDPs and Bellman operators to this new framework.

Keywords

Reinforcement learning Markov Decision Process configurable Markov Decision Process

1 Introduction

Reinforcement Learning [RL, 43] has attracted significant attention, in the last decade, as an effective approach to addressing complex control tasks when the knowledge of the underlying environment is not available. Remarkable successes have been achieved in industrial robot control [10], trading [7], playing videogames [30], and autonomous driving [14]. RL is rooted in the particular nature of the interaction between the artificial agent and the environment. The agent observes the state of the environment, performs an action, and the environment responds by evolving to the new state and providing the agent with a reward signal. The agent’s goal consists in maximizing the expected cumulative reward (possibly discounted) collected during its experience in the environment. This form of interaction is modeled with the Markov Decision Process [MDP, 37] formalism.

Although simple and intuitive, this kind of interaction rules out a number of real-world scenarios of interest. Indeed, in the traditional formalism, the environment is considered a fully passive entity, whose dynamics is fixed and cannot be altered. Although some approaches did account for a changing environment; the majority of the literature has focused on non-stationary evolution [12, 13] in which the dynamics naturally modifies, independently of the agent activity. Instead, there exist several realistic scenarios in which a limited interventional power over the environment is possible. Such intervention on some environmental parameters, usually possible to a confined extent and more expensive than policy learning, is called environment configuration.

The Configurable Markov Decision Process [Conf-MDP, 17, 18, 23] framework has emerged in the last three years as a useful approach to model and analyze the scenarios in which it is possible to configure some parameters of the environments, with an effect on the environment transition probabilities. The entity entitled to this modification can be either the agent itself or an external configurator. The literature [17] has considered a surge of settings that differ according to several dimensions. The main distinction is between cooperative and non-cooperative Conf-MDPs. In the former case, the agent and the entity entitled to carry out the configuration activity share the same goal, modeled by a unique reward function. Instead, in the latter case, agent and configurator, which are now clearly distinct entities, have different goals, inducing different levels of strategic behavior. Before proceeding further, let us consider the following two examples.

Example 1.1. (Car Driving). Consider the setting of a driver that wants to learn how to drive an F1 car. The car is a part of the environment, but some of its features can be configured, while other portions of the environment cannot (e.g., physical laws). For instance, we can change the kind of tires, the brake repartition between front and rear, and the wing orientation. The effect of these vehicle elements impact the transition probabilities of the environment. We observe that the configuration activity can be carried out by the agent itself or by some external configurator (e.g., a track engineer). Furthermore, the goal of the configuration can be multiple. The agent might be interested in finding the vehicle that best fits its driving abilities, or the track engineer might want to provide the agent with vehicles of increasing difficulty to guide the agent learning process. In both cases, however, the agent and the configurator (the agent itself or the track engineer) share the same objective, i.e., improving the agent learning experience. Thus, we are in a cooperative setting.

Example 1.2. (Supermarket). Suppose we are the owner of a supermarket and we have to decide how to place the goods on the shelves. The goods placement is a feature of the environment that can be subject to configuration by the supermarket owner, that plays the role of the configurator. Their goal consists in maximizing the supermarket profit by inducing, for instance, the customers to spend as much time as possible in the supermarket. The customers, instead, represent the agents in this problem and might have an objective that is different from that of the supermarket owner. For instance, the customers want to find the goods they are interested in, minimizing the time spent inside the supermarket. Thus, in this setting, differently from the previous case, the agents (customers) and the configurator (supermarket owner) have diverging interests, i.e., we are in a non-cooperative setting.

In this paper, we provide a unified presentation of methods and approaches to deal with Conf-MDPs. The goal of this paper is to provide a common notation and extend the traditional tools employed for MDPs (e.g., value functions and Bellman operators) to Conf-MDPs. Furthermore, we want to take stock of the advancements in this novel area. We start in Section 2 with a review of the literature about Conf-MDPs, focusing on modelization, algorithms, and theoretical results. In Section 3, we introduce the notation and the background needed in the subsequent sections. In Section 4, we introduce and discuss the general definition of Conf-MDP, while in Section 5, we extend the traditional value functions to the case of Conf-MDPs together with the corresponding Bellman operators. Moreover, we prove that those operators preserve the contraction property and, consequently, they can be employed to iteratively compute the value functions. Then, in Section 6, we introduce the notion of policy and configuration best responses, together with the corresponding value functions and operators. We show that finding the policy and configuration best responses can be reduced to the solution of a traditional MDP. Section 7 is devoted to the presentation of the cooperative setting, for which we introduce the solution concept, operators and value functions. Moreover, we illustrate that solving a cooperative Conf-MDP is equivalent to solving a suitably defined deterministic MDP. In Section 8, we move to the non-cooperative setting providing a first distinction between turn-based and leader-follower Conf-MDPs, based on the kind of interaction taking place between agent and configurator. In Section 9, we focus on the turn-based setting. We first reduce the turn-based Conf-MDP to a suitably defined turn-based Markov Game (MG). We highlight the existence of the Nash equilibrium, and we define the corresponding value functions. The particular case of zero-sum Conf-MDPs, in which agent and configurator display fully competitive interests, is addressed in Section 10. For this setting, we provide the value functions and the corresponding Bellman operators, studying their properties. We move to the leader-follower setting in Section 11, adapting the notion of Stackelberg equilibrium to the Conf-MDPs and providing value functions and operators. We conclude in Section 12 summarizing the results and suggesting future research directions. Part of the results reported in this paper was presented in the Ph.D. dissertation [17].

2 Literature review

In this section, we survey the literature in order to provide a complete presentation of the formalizations, methods, and algorithmic approaches to address environment configurability. Table 1 summarizes the reviewed papers.

Table 1
Schematic comparison among the papers reviewed in Section 2

Paper Framework Cooperative vs non-cooperative Planning vs learning Configuration cost Theory Algorithms Applications

[23] Conf-MDP Cooperative Planning ✗ ✓ ✓ ✗

[19] Conf-MDP Cooperative Learning ✗ ✓ ✓ ✗

[41] Conf-MDPs Cooperative Planning ✓ ✓ ✓ ✗

[49] Environment design Non-cooperative Planning ✓ ✓ ✓ ✗

[48] Environment design Non-cooperative Planning ✓ ✓ ✓ ✗

[50] Policy teaching Non-cooperative Planning ✗ ✓ ✓ ✗

(Environment design)

[11] Environment design Cooperative Planning ✓ ✓ ✓ ✗

[42] MDP Cooperative Learning ✓ ✗ ✓ ✗

[5] MDP Non-cooperative Learning ✗ ✗ ✓ ✓

(Rare events)

[21] Conf-MDP Cooperative Learning ✗ ✗ ✓ ✓

(Policy space identification)

[22] Conf-MDP Cooperative Learning ✗ ✗ ✓ ✓

(Control frequency adaptation)

[39] Conf-MDP Non-cooperative Learning ✗ ✓ ✓ ✗

[16] Policy poisoning Non-cooperative Learning ✗ ✓ ✓ ✗

Paper	Framework	Cooperative vs non-cooperative	Planning vs learning	Configuration cost	Theory	Algorithms	Applications
[23]	Conf-MDP	Cooperative	Planning	✗	✓	✓	✗
[19]	Conf-MDP	Cooperative	Learning	✗	✓	✓	✗
[41]	Conf-MDPs	Cooperative	Planning	✓	✓	✓	✗
[49]	Environment design	Non-cooperative	Planning	✓	✓	✓	✗
[48]	Environment design	Non-cooperative	Planning	✓	✓	✓	✗
[50]	Policy teaching	Non-cooperative	Planning	✗	✓	✓	✗
	(Environment design)
[11]	Environment design	Cooperative	Planning	✓	✓	✓	✗
[42]	MDP	Cooperative	Learning	✓	✗	✓	✗
[5]	MDP	Non-cooperative	Learning	✗	✗	✓	✓
							(Rare events)
[21]	Conf-MDP	Cooperative	Learning	✗	✗	✓	✓
							(Policy space identification)
[22]	Conf-MDP	Cooperative	Learning	✗	✗	✓	✓
							(Control frequency adaptation)
[39]	Conf-MDP	Non-cooperative	Learning	✗	✓	✓	✗
[16]	Policy poisoning	Non-cooperative	Learning	✗	✓	✓	✗

The notion of configurable environment has been introduced in [23], in its cooperative form. In the same work, a learning algorithm, Safe Policy Model Iteration (SPMI) was proposed. SPMI is applicable to finite state-action environments and under the assumption, the effect of the configurable parameters on the transition probabilities is known to the learner. The resulting algorithm, endowed with strong theoretical guarantees on the performance improvement, was tested on illustrative domains. In [19], the main limitations of SPMI were addressed by proposing a novel approach, Relative Entropy Model Policy Search (REMPS), belonging to the class of trust-region methods. REMPS is able to learn in presence of parametric policy and configuration models and does not require knowing in advance the effect of the configurable parameters, which, instead, are inferred by interacting with the environment. The algorithm was tested on a realistic car configuration task, based on the TORCS simulator, showing the advantages of employing environment configuration over fixed-configuration learning. Recently, it has been proved that, in the cooperative setting, when the configurator has access to a limited configuration space, finding the optimal configuration is an NP-hard problem [41].

The idea of intervening in the environment features with the goal of inducing a specific behavior of the agent was considered in previous works about environment design [48, 49]. In this framework, introduced by the planning community, there exists an interested party, compatible with the notion of configurator, that is allowed to alter dynamically the reward function and the transition dynamics in order to induce a specific behavior of the agent. In this setting, the agent is assumed to be unaware of the interested party presence and, consequently, it acts as a best responder. However, the interested party is assumed to know how the agent will react to any environment proposed, which does not need to be an MDP. Subsequent papers considered specific teaching purposes [50]. Among the environment design approaches, the equi-reward utility maximization design [11] considers the case in which the interested party displays the same goal as the agent. In this case, the formulation is restricted to the MDP case and the interested party task is to plan an optimal sequence of environment changes so as to maximize the agent’s performance.

To account for the possibility that configuring the environment can be an expensive task, in [42] an approach to environment configuration that embeds in the objective function a notion of cost is proposed. The goal is to find the environment that favors the agent learning, regularizing with the cost of implementing a specific configuration. The notion of environment configurability has been employed coped with policy gradient approaches, with the goal of reducing the variance of the gradient estimation, in combination with off-policy methods [25 , 34], by increasing the probability of rare events [5]. Another application of Conf-MDPs is policy space identification [21]. In this setting, the task consists in identifying the capabilities of the agent in terms of perception and actuation. Altering the environment can induce the agent to reveal its capabilities in a more effective way. Furthermore, in [22], a specific environmental parameter, the control frequency, is configured with visible advantages on the learning performance in the context of batch RL algorithms.

Among the approaches that consider the presence of a configurator displaying a goal explicitly diverging from that of the agent we mention [39]. In this work, a regret minimization approach is proposed in the case in which the agent and configurator have arbitrary reward functions. The model resembles the leader-follower interaction, in which the configurator commits to a configuration and the agent is a best responder with a limited strategic power. From a certain perspective, policy poisoning [16] can be considered a form of environment configuration in which the goal of the configurator is to make the agent play a specific policy, by acting either on the reward function or on the transition dynamics.

3 Preliminaries

In this section, we introduce the necessary background that will be employed in the remainder of the paper.

3.1 Notation

Let $X$ be a finite set, we denote with $Δ^{X} = {ν \in [0, 1]^{X} : \sum_{x \in X} ν (x) = 1}$ the simplex over $X$ . Let $Y$ another finite set, we denote with $Δ_{Y}^{X}$ the set of functions $Y \to Δ^{X}$ . Let $f \in ℝ^{X}$ , we denote with ${Id}_{X} : ℝ^{X} \to ℝ^{X}$ the identity operator $(I d_{X} f) (x) = f (x)$ , with $M_{X} : ℝ^{X} \to ℝ$ the max operator $M_{X} f = max_{x \in X} {f (x)}$ , and with $∥ f ∥_{\infty} = M_{X} | f |$ the L_∞-norm.

3.2 Markov Decision Processes

An infinite-horizon discounted finite Markov Decision Process [MDP, 37] is defined as a 5-tuple $M = (S, A, p, r, γ)$ , where $S$ is a finite set of states, $A$ is a finite set of actions, $p \in Δ_{S \times A}^{S}$ is the transition model mapping every state-action pair $(s, a) \in S \times A$ to a probability distribution of the next state p (· |s, a), $r \in ℝ^{S \times A \times S}$ is the reward function mapping every state-action-next-state triple $(s, a, s^{'}) \in S \times A \times S$ to the corresponding reward r (s, a, s′), and γ ∈ [0, 1) is the discount factor. The agent’s behavior is modeled by a policy $π \in Δ_{S}^{A}$ mapping every state $s \in S$ to a probability distribution over the actions π (· |s).

Interaction Protocol. At each step $t \in ℕ$ , the agent observes the environment state $s_{t} \in S$ , plays an action $a_{t} \in A$ sampled from its policy π (· |s_t), the environment evolves to the next state $s_{t + 1} \in S$ according to its transition model p (· |s_t, a_t), provides the agent with a reward r (s_t, a_t, s_t+1), and the process repeats.

Operators. Let $g \in ℝ^{S \times A}$ , we denote with $Π : ℝ^{S \times A} \to ℝ^{S}$ the policy operator induced by policy $π \in Δ_{S}^{A}$ , defined as: $\begin{matrix} (Π g) (s) = \sum_{a \in A} π (a | s) g (s, a), \forall s \in S . \end{matrix}$ Let $f \in ℝ^{S}$ , we denote with $P : ℝ^{S} \to ℝ^{S \times A}$ the transition model operator induced by transition model $p \in Δ_{S \times A}^{S}$ , defined as: $\begin{matrix} (Pf) (s, a) = \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'}), \forall (s, a) \in S \times A . \end{matrix}$ In particular, we define the expected rewards for every state-action pair $(s, a) \in S \times A$ : $\begin{matrix} r_{p} (s, a) = \sum_{s^{'} \in S} p (s^{'} | s, a) r (s, a, s^{'}), \\ r_{π, p} (s) = (Π r) (s) = \sum_{a \in A} π (a | s) r (s, a) . \end{matrix}$ Furthermore, we introduce the following inverse operators via the Neumann series: $\begin{matrix} {(I d_{S} - γ Π P)}^{- 1} f = \sum_{t = 0}^{+ \infty} γ^{t} {(Π P)}^{t} f, \\ {(I d_{S \times A} - γ P Π)}^{- 1} g = \sum_{t = 0}^{+ \infty} γ^{t} {(P Π)}^{t} g . \end{matrix}$

Value Functions. A policy $π \in Δ_{S}^{A}$ in an MDP induces a value function [43] $v_{π} \in ℝ^{S}$ , defined as the expected discounted sum of the rewards obtained by executing policy π from a state $s \in S$ : $\begin{matrix} v_{π} (s) & : = 𝔼_{π} [\sum_{t = 0}^{+ \infty} γ^{t} r (s_{t}, a_{t}, s_{t + 1}) | s_{0} = s] \\ = ({(I d_{S} - γ Π P)}^{- 1} r_{π, p}) (s), \end{matrix}$ where we denote with $𝔼_{π}$ the expectation w.r.t the state-action visitation distribution induced by policy π. The optimal value function $v_{*} \in ℝ^{S}$ is defined for every state $s \in S$ as: $\begin{matrix} v_{*} (s) & : = sup_{π \in Δ_{S}^{A}} {v_{π} (s)} . \end{matrix}$ A policy $π^{*} \in Δ_{S}^{A}$ is optimal if it maximizes the value function starting from every state, i.e., if v_{π
^*} (s) = v_* (s) for every $s \in S$ . It is well-known that in an MDP a deterministic optimal policy exists [37]. The optimal policies can be derived as greedy policies w.r.t the optimal value function v_*, i.e., for every state $s \in S$ : $\begin{matrix} π^{*} (\cdot | s) \in Δ^{G (s)}, where \\ G (s) : = {argmax}_{a \in A} {r_{p} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) v_{*} (s^{'})}, \end{matrix}$ where $G (s)$ is the set of the greedy actions.

Bellman Operators. The value functions v_π and v_* can be computed by means of the iterative application of suitably defined Bellman operators [2]. Let $π \in Δ_{S}^{A}$ be a policy, the Bellman expectation operator $B_{π} : R^{S} \to R^{S}$ is defined for every $f \in ℝ^{S}$ and $s \in S$ as: $\begin{matrix} B_{π} (s) & = (r_{π, p} + γ Π Pf) (s) \\ = r_{π, p} (s) + γ \sum_{a \in A} π (a | s) \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'}) . \end{matrix}$ $B_{π}$ is a linear operator and a γ-contractions in L_∞-norm. Thus, it admits a unique fixed point represented by the value function v_π. The optimal Bellman operator $B_{*} : R^{S} \to R^{S}$ is defined for every $f \in ℝ^{S}$ and $s \in S$ as: $\begin{matrix} B_{*} [f] (s) = (M_{A} (r_{p} + γ Pf)) (s) \\ = max_{a \in A} {r_{p} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'})} . \end{matrix}$ $B_{*}$ is no longer linear but it remains a γ-contractions in L_∞-norm and its unique fixed point is the optimal value function v_* [37].

3.3 Two-players turn-based Markov Games

An infinite-horizon discounted finite two-players turn-based Markov Game [MG, 15, 40] is defined as a 8-tuple $G = (S_{1}, S_{2}, A_{1}, A_{2}, p, r_{1}, r_{2}, γ)$ , where $S_{1}$ and $S_{2}$ are finite set of states in which the first and the second player are entitled to play respectively with $S : = S_{1} \cup S_{2}$ , $A_{1}$ and $A_{2}$ are finite set of actions for the first and second player respectively and $A : = A_{1} \cup A_{2}$ , $p \in Δ_{S \times A}^{S}$ is the transition model mapping every pair 1 $(s, a) \in S \times A$ to the probability distribution of the next state p (· |s, a), $r_{1}, r_{2} \in ℝ^{S \times A \times S}$ are the reward functions of the first and second player respectively, and γ ∈ [0, 1) is the discount factor. The agents’ behaviors are defined in terms of policies $π_{1} \in Δ_{S_{1}}^{A_{1}}$ and $π_{2} \in Δ_{S_{2}}^{A_{2}}$ for the first and second player respectively.

Interaction Protocol. At each step $t \in ℕ$ , both players observe the state of the environment $s_{t} \in S$ . If $s \in S_{1}$ (resp. $s \in S_{2}$ ) is the turn of the first (resp. second) player that takes an action $a_{t} \in A_{1}$ (resp. $a_{t} \in A_{2}$ ) according to its policy π₁ (· |s_t) (resp. π₂ (· |s_t)) that is observed by the other player too. The environment evolves to the next state $s_{t + 1} \in S$ according to the transition model p (· |s_t, a_t) and each player collects the reward r₁ (s_t, a_t, s_t+1) and r₂ (s_t, a_t, s_t+1) respectively and the process repeats.

Value Functions A pair of policies $π_{1} \in Δ_{S_{1}}^{A_{1}}$ and $π_{2} \in Δ_{S_{2}}^{A_{2}}$ in a MG induces the value functions $v_{π_{1}, π_{2}}^{1}, v_{π_{1}, π_{2}}^{2} \in ℝ^{S}$ for the two players, i.e., the expected discounted sum of the rewards obtained by executing policies π₁ and π₂ from a state $s \in S$ : $\begin{matrix} v_{π_{1}, π_{2}}^{1} (s) : = 𝔼_{π_{1}, π_{2}} [\sum_{t = 0}^{+ \infty} γ^{t} r_{1} (s_{t}, a_{t}, s_{t + 1}) | s_{0} = s], \\ v_{π_{1}, π_{2}}^{2} (s) : = 𝔼_{π_{1}, π_{2}} [\sum_{t = 0}^{+ \infty} γ^{t} r_{2} (s_{t}, a_{t}, s_{t + 1}) | s_{0} = s], \end{matrix}$ where we denote with $𝔼_{π_{1}, π_{2}}$ the expectation w.r.t the state-action visitation distribution induced by policies π₁ and π₂. The best response value functions $v_{*, π_{2}}^{1}, v_{π_{1}, *}^{1} : ℝ^{S}$ are defined for every state $s \in S$ as: $\begin{matrix} v_{*, π_{2}}^{1} (s) : = sup_{π_{1} \in Δ_{S_{1}}^{A_{1}}} {v_{π_{1}, π_{2}}^{1} (s)}, \\ v_{π_{1}, *}^{2} (s) : = sup_{π_{2} \in Δ_{S_{2}}^{A_{2}}} {v_{π_{1}, π_{2}}^{2} (s)} . \end{matrix}$ A pair of policies $(π_{1}^{*}, π_{2}^{*}) \in Δ_{S_{1}}^{A_{1}} \times Δ_{S_{2}}^{A_{2}}$ is a Nash equilibrium if no player has interest in unilaterally deviate from the equilibrium, i.e., for every state $s \in S$ we have: $v_{π_{1}^{*}, π_{2}^{*}}^{1} (s) = v_{*, π_{2}^{*}}^{1} (s)$ and $v_{π_{1}^{*}, π_{2}^{*}}^{2} (s) = v_{π_{1}^{*}, *}^{2} (s)$ . We say that a turn-based MG is alternating if every turn of the first player is followed by a turn of the second player and vice versa, i.e., if the following conditions hold: $\begin{matrix} p (\cdot | s_{1}, a_{1}) \in Δ^{S_{2}}, \forall (s_{1}, a_{1}) \in S_{1} \times A_{1}, \\ p (\cdot | s_{2}, a_{2}) \in Δ^{S_{1}}, \forall (s_{2}, a_{2}) \in S_{2} \times A_{2} . \end{matrix}$

Bellman Operators. In the case of alternating turn-based MGs, we introduce the following Bellman operators [9] $B_{π_{1}, π_{2}}^{1}, B_{π_{1}, π_{2}}^{2} : ℝ^{S} \to ℝ^{S}$ , defined for every $f \in ℝ^{S}$ and $s \in S$ : $\begin{matrix} B_{π_{1}, π_{2}}^{1} [f] (s) \\ = {\begin{matrix} (Π_{1} (r_{1} + γ P Π_{2} (r_{1} + γ Pf))) (s) & if s \in S_{1} \\ (Π_{2} (r_{1} + γ P Π_{1} (r_{1} + γ Pf))) (s) & if s \in S_{2} \end{matrix}, \\ B_{π_{1}, π_{2}}^{2} [f] (s) \\ = {\begin{matrix} (Π_{1} (r_{2} + γ P Π_{2} (r_{2} + γ Pf))) (s) & if s \in S_{1} \\ (Π_{2} (r_{2} + γ P Π_{1} (r_{2} + γ Pf))) (s) & if s \in S_{2} \end{matrix} . \end{matrix}$ The rationale behind these operators is that of applying alternatively policies π₁ and π₂, based on whether the initial state s belongs to $S_{1}$ or $S_{2}$ . These operators are γ²-contractions in L_∞-norm and their unique fixed points correspond to the value functions $v_{π_{1}, π_{2}}^{1}$ and $v_{π_{1}, π_{2}}^{2}$ respectively.

4 Model formulation

In this section, we introduce and discuss the definition of Configurable Markov Decision Process [Conf-MDP, 17, 18, 21–23, 39]. As we mentioned above, a Conf-MDP can be regarded as a traditional MDP with the additional possibility to configure some environmental parameters leading to a modification of the transition probabilities. Furthermore, the presence of the agent and configurator pursuing possibly different goals, requires considering two reward functions.

4.1 Definition

For the sake of this paper, we limit to the case of finite states and actions, although most of the results can be extended to the continuous setting.

Definition 4.1. (Configurable Markov Decision Process). A discrete-time infinite-horizon discounted finite Configurable Markov Decision Process (Conf-MDP) is defined as a 5-tuple $C = (S, A, r^{A}, r^{C}, γ)$ where $S$ is a finite state space, $A$ is a finite action space, $r^{A}, r^{C} : ℝ^{S \times A \times S}$ are the agent and configurator reward functions respectively, and γ ∈ [0, 1) is the discount factor.

The definition of Conf-MDP is obtained from that of the MDP by neglecting the transition model p, that we will also call configuration in the following, and considering two reward functions: one for the agent r^A and one for the configurator r^C. It is worth noting that in Definition 4.1, we considered reward functions depending on the next state too. While for traditional MDPs, focusing on reward functions depending on the current state-action pair is without loss of generality as the transition model is fixed, for the Conf-MDPs the dependence on the next state is essential as the transition model can be altered as an effect of environment configuration [17]. A graphical representation of the MDP and the Conf-MDP framework is reported in Fig. 1.

Fig. 1

Graphical representation of the interaction between an agent and an environment in an MDP (left) and in a Conf-MDP (right).

4.2 Policies and configurations

In a Conf-MDP, the agent is entitled of choosing a policy π, mapping states to actions (like in traditional MDPs), and the configurator is in charge of selecting a configuration, i.e., a transition model p mapping state-action pairs to next states. Concerning the policy, we limit to the case of Markovian stationary policies $π \in Δ_{S}^{A}$ mapping states $s \in S$ to probability distributions over actions π (· |s). Concerning the configuration, we define a Markovian stationary configuration (or transition model) $p \in Δ_{S \times A}^{S}$ as a function mapping state-action pairs $(s, a) \in S \times A$ to probability distributions over states p (s′|s, a) with $s^{'} \in S$ . 2

5 Value functions

In this section, we introduce the notion of value function for Conf-MDPs. We extend the analogous concept defined for standard RL [43], representing the expected discounted sum of the rewards collected during an interaction between agent and environment. For this purpose, we introduce the operator $𝔼_{π, p}$ to denote the expectation w.r.t the state-action visitation distribution induced by policy π and configuration p.

Definition 5.1. (Value Functions). Let $π \in Δ_{S}^{A}$ be a policy, and $p \in Δ_{S \times A}^{S}$ be a configuration. The agent value function $υ_{π, p}^{A} : ℝ^{S}$ is defined for all states $s \in S$ as: $\begin{matrix} υ_{π, p}^{A} (s) & = 𝔼_{π, p} [\sum_{t = 0}^{+ \infty} γ^{t} r^{A} (s_{t}, a_{t}, s_{t + 1}) | s_{0} = s] \\ = ({(I d_{S} - γ Π P)}^{- 1} r_{π, p}^{A}) (s) . \end{matrix}$ The configurator value function $q_{π, p}^{C} : ℝ^{S \times A}$ is defined for all state-action pairs $(s, a) \in S \times A$ as: $\begin{matrix} q_{π, p}^{C} (s, a) & = 𝔼_{π, p} [\sum_{t = 0}^{+ \infty} γ^{t} r^{C} (s_{t}, a_{t}, s_{t + 1}) | (s_{0}, a_{0}) = (s, a)] \\ = ({(I d_{S \times A} - γ P Π)}^{- 1} r_{p}^{C}) (s, a) . \end{matrix}$

It is worth noting that since the agent is entitled to perform actions, we define its value $υ_{π, p}^{A} (s)$ as a function of the state $s \in S$ only, whereas, since the configurator decides the next state, having observed the agent’s action, its value $q_{π, p}^{C} (s, a)$ is a function of the state-action pair $(s, a) \in S \times A$ .

5.1 Agent and configurator Bellman operators

In full analogy with traditional RL [37], we can express these value functions by means of suitable recursive relations which are formalized by Bellman equations [2]. To this purpose, we now introduce the Bellman expectation operators.

Definition 5.2. (Bellman Expectation Operators). Let $π \in Δ_{S}^{A}$ be a policy and $p \in Δ_{S \times A}^{S}$ be a configuration. The agent Bellman expectation operator $B_{π, p}^{A} : R^{S} \to R^{S}$ is defined for all functions $f \in ℝ^{S}$ for all states $s \in S$ as: $\begin{matrix} B_{π, p}^{A} [f] (s) & = (r_{π, p}^{A} + γ Π Pf) (s) \\ = r_{π, p}^{A} (s) + γ \sum_{a \in A} π (a | s) \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'}) . \end{matrix}$ The configurator Bellman expectation operator $B_{π, p}^{C} : R^{S \times A} \to R^{S \times A}$ is defined for all functions $g \in ℝ^{S \times A}$ for all state-action pairs $(s, a) \in S \times A$ as: $\begin{matrix} B_{π, p}^{C} [g] (s, a) = (r_{p}^{C} + γ P Π g) (s, a) \\ = r_{p}^{C} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) \sum_{a^{'} \in A} π (a^{'} | s^{'}) g (s^{'}, a^{'}) . \end{matrix}$

The operators $B_{π, p}^{A}$ and $B_{π, p}^{C}$ are in all regards the traditional Bellman expectation operators for the state-value function and state-action-value function. Therefore, they fulfill the following properties regarding contraction and fixed points [37].

Proposition 5.1. The Bellman expectation operators $B_{π, p}^{A}$ and $B_{π, p}^{C}$ are γ-contractions in L_∞-norm, i.e., for all $f, f^{'} \in ℝ^{S}$ and $g, g^{'} \in ℝ^{S \times A}$ : $\begin{matrix} {∥ B_{π, p}^{A} [f] - B_{π, p}^{A} [f^{'}] ∥}_{\infty} \leq γ {∥ f - f^{'} ∥}_{\infty}, \\ {∥ B_{π, p}^{C} [g] - B_{π, p}^{C} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ Moreover, the agent value function $υ_{π, p}^{A}$ and the configurator value function $q_{π, p}^{C}$ are their unique fixed points respectively: $\begin{matrix} υ_{π, p}^{A} = B_{π, p}^{A} [υ_{π, p}^{A}], q_{π, p}^{C} = B_{π, p}^{C} [q_{π, p}^{C}] . \end{matrix}$

Proof: We prove the statement for the configurator operator $B_{π, p}^{C}$ , as the proof for the agent case is analogous: $\begin{matrix} B_{π, p}^{C} [g] - B_{π, p}^{C} [g^{'}] & = r_{p}^{C} + γ P Π g - r_{p}^{C} + γ P Π g^{'} \\ = γ P Π (g - g^{'}) . \end{matrix}$ By taking the L_∞-norm, we obtain: $\begin{matrix} {∥ B_{π, p}^{C} [g] - B_{π, p}^{C} [g^{'}] ∥}_{\infty} & = γ {∥ P Π (g - g^{'}) ∥}_{\infty} \\ \leq γ {∥ P Π ∥}_{\infty} {∥ g - g^{'} ∥}_{\infty} \\ = γ {∥ g - g^{'} ∥}_{\infty}, \end{matrix}$ where we observed that ∥PΠ ∥ _∞ = 1 being PΠ a stochastic matrix. Thus, $B_{π, p}^{C}$ is a γ-contraction. As γ < 1 and $(ℝ^{S \times A}, d_{\infty})$ is a non-empty complete metric space where d_∞ is the metric induced by the L_∞-norm, thanks to the Banach fixed point theorem, we have that $B_{π, p}^{C}$ admits a unique fixed point. It is immediate to prove that $q_{π, p}^{C}$ is the fixed point. □

5.2 Value function computation

Algorithm 1 shows how to iteratively compute the fixed-point value functions. It repeatedly performs the application of the Bellman expectation operators until a convergence threshold is achieved. The following result derives the per-iteration time complexity of the algorithm and an upper bound on the number of iterations needed for convergence.

Theorem 5.2. (Algorithm 1). The per-iteration time complexity of Algorithm 1 is $O (| S |^{2} | A |^{2})$ . If ∥r^A ∥ _∞ ≤ R and ∥r^C ∥ _∞ ≤ R, then Algorithm 1 terminates in at most $\begin{matrix} ⌈ \frac{log \frac{R (1 + γ)}{ɛ (1 - γ)}}{log \frac{1}{γ}} ⌉ iterations, \end{matrix}$ with the guarantee: $\begin{matrix} {∥ v^{A} - υ_{π, p}^{A} ∥}_{\infty} \leq \frac{ɛ}{1 - γ}, {∥ q^{A} - q_{π, p}^{A} ∥}_{\infty} \leq \frac{ɛ}{1 - γ} . \end{matrix}$

Proof: The time complexity is dominated by the application of $B_{π, p}^{C}$ that requires for each state-action pair $(s, a) \in S \times A$ two nested summations over $S \times A$ . Therefore, the per-iteration time complexity is $O (| S |^{2} | A |^{2})$ .

Let $v_{i}^{A}$ be the value function approximated at the beginning of iteration i ≥ 1. By exploiting the γ-contraction of Proposition 5.1, we have: $\begin{matrix} {∥ v_{i + 1}^{A} - v_{i}^{A} ∥}_{\infty} & \leq {∥ v_{i + 1}^{A} - υ_{π, p}^{A} ∥}_{\infty} + {∥ υ_{π, p}^{A} - v_{i}^{A} ∥}_{\infty} \\ \leq γ^{i + 1} {∥ 0 - υ_{π, p}^{A} ∥}_{\infty} + γ^{i} {∥ υ_{π, p}^{A} - 0 ∥}_{\infty} \\ \leq γ^{i} (1 + γ) {∥ υ_{π, p}^{A} ∥}_{\infty} \\ \leq \frac{γ^{i} (1 + γ) R}{1 - γ}, \end{matrix}$ having exploited that ${∥ υ_{π, p}^{A} ∥}_{\infty} \leq \frac{R}{1 - γ}$ . By enforcing the last equation ≤ɛ, we have: $\begin{matrix} i \leq \frac{log \frac{R (1 + γ)}{ɛ (1 - γ)}}{log \frac{1}{γ}} . \end{matrix}$ For the second statement, recalling that $v_{i + 1}^{A} = B_{π, p}^{A} [v_{i}^{A}]$ and $υ_{π, p}^{A} = B_{π, p}^{A} [υ_{π, p}^{A}]$ and using Proposition 5.1, we have: $\begin{matrix} {∥ υ_{π, p}^{A} - v_{i}^{A} ∥}_{\infty} & \leq {∥ υ_{π, p}^{A} - v_{i + 1}^{A} ∥}_{\infty} + {∥ v_{i + 1}^{A} - v_{i}^{A} ∥}_{\infty} \\ \leq {∥ B_{π, p}^{A} [υ_{π, p}^{A}] - B_{π, p}^{A} [v_{i}^{A}] ∥}_{\infty} + ɛ \\ \leq γ {∥ υ_{π, p}^{A} - v_{i}^{A} ∥}_{\infty} + ɛ . \end{matrix}$ From which, we obtain: $\begin{matrix} {∥ υ_{π, p}^{A} - v_{i}^{A} ∥}_{\infty} \leq \frac{ɛ}{1 - γ} . \end{matrix}$ The proof is fully analogous concerning the configurator value function. □

Algorithm 1. Agent-Configurator Evaluation (A-C-EVAL)
procedureA-C-EVAL(policy π, configuration p, error ɛ)
Initialize v^A (s) ←0 for all $s \in S$
Initialize q^C (s, a) ←0 for all $(s, a) \in S \times A$
do
${\tilde{v}}^{A} \leftarrow v^{A}$
${\tilde{q}}^{C} \leftarrow q^{C}$
$v^{A} \leftarrow B_{π, p}^{A}$
$q^{C} \leftarrow B_{π, p}^{C} [{\tilde{q}}^{C}]$
while ${∥ v^{A} - {\tilde{v}}^{A} ∥}_{\infty} > ɛ$ or ${∥ q^{C} - {\tilde{q}}^{C} ∥}_{\infty} > ɛ$
returnv^A, q^C
end procedure

6 Best responses

A Conf-MDP involves the interaction of two entities, the agent and the configurator each playing a policy π and a configuration p respectively. In full analogy with what is done in game theory [40], it is convenient to define the notion of best response policy and configuration. To this end, we start by introducing the concept of best response value function.

Definition 6.1. (Best Response Value Functions). Let $p \in Δ_{S \times A}^{S}$ be a configuration. The agent best response value function $υ_{*, p}^{A} : ℝ^{S}$ to confiuguration p is defined for every states $s \in S$ as: $\begin{matrix} υ_{*, p}^{A} (s) & = sup_{π \in Δ_{S}^{A}} {υ_{π, p}^{A} (s)} . \end{matrix}$ Let $π \in Δ_{S}^{A}$ be a policy. The best response configurator value function $q_{π, *}^{C} : ℝ^{S \times A} \to ℝ$ to policy π is defined for every state-action pair $(s, a) \in S \times A$ as: $\begin{matrix} q_{π, *}^{C} (s, a) & = sup_{p \in Δ_{S \times A}^{S}} {q_{π, p}^{C} (s, a)} . \end{matrix}$

Furthermore, we say that a policy $π_{p}^{*} \in Δ_{S}^{A}$ is a best response policy w.r.t the configuration $p \in Δ_{S}^{A}$ if it holds for all $s \in S$ that: $\begin{matrix} υ_{π_{p}^{*}, p}^{A} (s) = υ_{*, p}^{A} (s), \end{matrix}$ i.e., if it attains the agent best response value function. We denote with ${BR}^{A} (p) \subseteq Δ_{S}^{A}$ the set of all best response policies w.r.t configuration p. Similarly, we say that a configuration $p_{π}^{*} \in Δ_{S \times A}^{S}$ is a best response configuration w.r.t policy $π \in Δ_{S}^{A}$ if it holds for all $(s, a) \in S \times A$ that: $\begin{matrix} q_{π, p_{π}^{*}}^{C} (s, a) = q_{π, *}^{C} (s, a), \end{matrix}$ that is, if it attains the configurator best response value function. We denote with ${BR}^{C} (π) \subseteq Δ_{S \times A}^{S}$ the set of all best response configurations w.r.t policy π.

6.1 Existence of best response policies and configurations

In principle, we might wonder if best response policies and best response configuration do exist. This question is not trivial as, by Definition 6.1, the maximization is carried out for every state s and state-action pair (s, a) possibly leading to different best responses. Instead, we have defined a best response policy and configuration as a unique policy or configuration attaining the best response value function.

Concerning the existence of the best response policy $π_{p}^{*}$ , we observe that its determination consists, in all regards, to the solution of a traditional MDP with transition model p. Therefore, its existence is ensured and it can be any policy fulfilling the greedy condition for every $s \in S$ : $π_{p}^{*} (\cdot | s) \in Δ^{G^{A} (s)}, where$ (1) $G^{A} (s) : = \underset{a \in A}{argmax} {r_{p}^{A} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) υ_{*, p} (s^{'})} .$ Instead, for the existence of the configuration best response value function, we prove in Theorem 6.1 that we can reduce its determination to the solution of a suitably defined MDP. Therefore, its existence is guaranteed too, by means of the greedy configuration defined for every $(s, a) \in S \times A$ : $p_{π}^{*} (\cdot | s, a) \in Δ^{G^{C} (s, a)}, where$ (2) $\begin{matrix} G^{C} (s, a) \\ : = \underset{s^{'} \in S}{argmax} {r^{C} (s, a, s^{'}) + γ \sum_{a^{'} \in A} π (a^{'} | s^{'}) q_{π, *} (s^{'}, a^{'})} . \end{matrix}$ Specifically, the following result provides a reduction of the problems of computing the best response policy and configuration in a Conf-MDP to the problem of solving a traditional MDP.

Theorem 6.1. Let $C = (S, A, r^{A}, r^{C}, γ)$ be a Conf-MDP. Let $p \in Δ_{S \times A}^{S}$ be a configuration and ${\tilde{M}}^{A} = (S, A, p, r^{A}, γ)$ be an MDP. Then, for every $π \in Δ_{S}^{A}$ and every state $s \in S$ it holds that: $υ_{π, p}^{C, A} (s) = υ_{π}^{{\tilde{M}}^{A}} (s) .$ (3) Let $π \in Δ_{S}^{A}$ be a policy and let ${\tilde{M}}^{C} = (S \times A, S, {\tilde{p}}^{C}, {\tilde{r}}^{C}, γ)$ be an MDP defined as follows:

${\tilde{p}}^{C} : (S \times A) \times S \to Δ^{S \times A}$ , defined for every $((s, a), s^{'}) \in (S \times A) \times S$ and $(s^{″}, a^{″}) \in S \times A$ as:

${\tilde{r}}^{C} : (S \times A) \times S \times (S \times A) \to ℝ$ , defined for every $((s, a), s^{'}, (s^{″}, a^{″})) \in (S \times A) \times S \times (S \times A)$ as: ${\tilde{r}}^{C} ((s, a), s^{'}, (s^{″}, a^{″})) = r^{C} (s, a, s^{'}) .$

Then, for every $p \in Δ_{S \times A}^{S}$ , we define the policy ${\tilde{π}}^{C} : S \times A \to Δ^{S}$ for every state-action pair $(s, a) \in S \times A$ and $s^{'} \in S$ as:

\begin{matrix} {\tilde{π}}^{C} (s^{'} | s, a) = p (s^{'} | s, a) . \end{matrix}

Then, for every $p \in Δ_{S \times A}^{S}$ and for every state-action pair $(s, a) \in S \times A$ it holds that:

q_{π, p}^{C, C} (s, a) = υ_{{\tilde{π}}^{C}}^{{\tilde{M}}^{C}} (s, a) .

(4)

Proof: The first part of the theorem is straightforward. Concerning the second part, it suffices to prove that the Bellman operator associated to $(π, p) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ in the Conf-MDP $C$ , i.e., $B_{π, p}^{C, C}$ equals the Bellman operator associated to ${\tilde{π}}^{C}$ in the MDP ${\tilde{M}}^{C}$ , i.e., $B_{{\tilde{π}}^{C}}^{{\tilde{M}}^{C}}$ . Let $f \in ℝ^{S \times A}$ and let $(s, a) \in S \times A$ : □

Thus, we have shown that finding the best response policy in the Conf-MDP $C$ is equivalent to solve (i.e., finding the optimal policy) the MDP ${\tilde{M}}^{A}$ and, analogously, finding the best response configuration in the Conf-MDP $C$ is equivalent to solve the MDP ${\tilde{M}}^{C}$ .

6.2 Best response Bellman operators

We now introduce the best response Bellman operators and prove the corresponding contraction and fixed-point properties.

Definition 6.2. (Bellman Best Response Operators). Let $p \in Δ_{S \times A}^{S}$ be a configuration. The agent Bellman best response operator $B_{*, p}^{A} : R^{S} \to R^{S}$ to configuration p is defined for all $f \in ℝ^{S}$ as for all states $s \in S$ : $\begin{matrix} B_{*, p}^{A} [f] (s) & = (M_{A} (r_{p}^{A} + γ Pf)) (s) \\ = max_{a \in A} {r_{p}^{A} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'})} . \end{matrix}$ Let $π \in Δ_{S}^{A}$ be a policy. The configurator Bellman best response operator $B_{π, *}^{C} : R^{S \times A} \to R^{S \times A}$ to policy π is defined for all $g \in ℝ^{S \times A}$ as for all state-action pairs $(s, a) \in S \times A$ : $\begin{matrix} B_{π, *}^{C} [g] (s, a) = (M_{S} (r_{p}^{C} (s, a, \cdot) + γ Π g)) (s, a) \\ = max_{s^{'} \in S} {r^{C} (s, a, s^{'}) + γ \sum_{a^{'} \in A} π (a^{'} | s^{'}) g (s^{'}, a^{'})} . \end{matrix}$

We observe that the agent best response operator $B_{*, p}^{A}$ is equivalent to the optimal Bellman operator for traditional MDPs [37] and inherits all its properties. The following result generalizes the properties for the configurator best response operator $B_{π, *}^{C}$ .

Proposition 6.2. The Bellman best response operators $B_{*, p}^{A}$ and $B_{π, *}^{C}$ are γ-contractions in L_∞-norm, i.e., for all $f, f^{'} \in ℝ^{S}$ and $g, g^{'} \in ℝ^{S \times A}$ : $\begin{matrix} {∥ B_{*, p}^{A} [f] - B_{*, p}^{A} [f^{'}] ∥}_{\infty} \leq γ {∥ f - f^{'} ∥}_{\infty}, \\ {∥ B_{π, *}^{C} [g] - B_{π, *}^{C} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ Moreover, the agent best response value function $υ_{*, p}^{A}$ and the configurator best response value function $q_{π, *}^{C}$ are their unique fixed points respectively: $\begin{matrix} υ_{*, p}^{A} = B_{*, p}^{A} [υ_{*, p}^{A}], q_{π, *}^{C} = B_{π, *}^{C} [q_{π, *}^{C}] . \end{matrix}$

Proof: The operator $B_{*, p}$ is the traditional optimal Bellman operator, whose properties are known from [37]. We prove the statement for the configurator operator $B_{π, *}$ : $\begin{matrix} B_{π, *}^{C} [g] - B_{π, *}^{C} [g^{'}] \\ = M_{S} (r^{C} (_,_, \cdot) + γ Π q) - M_{S} (r^{C} (_,_, \cdot) + γ Π g^{'}) \\ \leq M_{S} | r^{C} (_,_, \cdot) + γ Π g - r^{C} (_,_, \cdot) + γ Π g^{'} | \\ \leq γ M_{S} | Π (g - g^{'}) |, \end{matrix}$ where with the symbol (_ , _ , ·) we denoted the fact that the operators are applied to the third argument only. By taking the L_∞-norm, we obtain: $\begin{matrix} {∥ B_{π, *}^{C} [g] - B_{π, *}^{C} [g^{'}] ∥}_{\infty} & \leq γ {∥ M_{S} | Π (g - g^{'}) | ∥}_{\infty} \\ \leq γ {∥ M_{S} Π ∥}_{\infty} {∥ g - g^{'} ∥}_{\infty} \\ \leq γ {∥ g - g^{'} ∥}_{\infty}, \end{matrix}$ where we observed that ${∥ M_{S} Π ∥}_{\infty} \leq 1$ . Since γ < 1 and $(ℝ^{S \times A}, d_{\infty})$ where d_∞ is the metric induced by the L_∞-norm, thanks to Banach fixed point theorem, the operator admits a unique fixed point. We now prove that if $g = B_{π, *}^{C} [g]$ then $g = q_{π, *}^{C}$ . We first prove that if $g \geq B_{π, *}^{C} [g]$ then $g \geq q_{π, *}^{C}$ . If $g \geq B_{π, *}^{C} [g]$ it means that for every $p \in Δ_{S \times A}^{S}$ it holds that $g \geq B_{π, p}^{C} [g]$ . Thus, we have for every $p \in Δ_{S \times A}^{S}$ : $\begin{matrix} g - q_{π, p}^{C} & \geq B_{π, p}^{C} [g] - B_{π, p}^{C} [q_{π, p}^{C}] = γ P Π (g - q_{π, p}^{C}) \geq 0, \end{matrix}$ where we exploited that for a function $h \in ℝ^{S \times A}$ if h ≥ γPΠh then $(I d_{S \times A} - γ P Π) h \geq 0$ that, in turn, implies h ≥ 0 if γ < 1 [Lemma 4.2, 31]. As $g \geq q_{π, p}^{C}$ for all $p \in Δ_{S \times A}^{S}$ , we have that $g \geq sup_{p \in Δ_{S \times A}^{S}} {q_{π, p}^{C}} = q_{π, *}^{C}$ . With an analogous argument we can prove that if $g \leq B_{π, *}^{C} [g]$ then $g \leq q_{π, *}^{C}$ . Combining the two results, we have proved that if $g = B_{π, *}^{C} [g]$ then $g = q_{π, *}^{C}$ . □

6.3 Best response computation

Algorithms 2 and 3 provide the pseudocode of the iterative algorithms to compute the best response value functions for the agent and the configurator respectively. They perform a repeated application of the Bellman best response operators until a given convergence threshold is reached. It is worth noting that both algorithms terminate with a number of iterations that can be bounded analogously to what is done in Theorem 5.2 thanks to the similar properties of the best response Bellman operators. Moreover, the final guarantee of Theorem 5.2 is preserved for both Algorithms 2 and 3: $\begin{matrix} {∥ v^{A} - υ_{*, p}^{A} ∥}_{\infty} \leq \frac{ɛ}{1 - γ}, {∥ q^{C} - q_{π, *}^{C} ∥}_{\infty} \leq \frac{ɛ}{1 - γ} . \end{matrix}$

Finally, we point out that once the best response value function is available, the computation of the best response policy or configuration is straightforward via Equations (1) and (2).

Algorithm 2. Agent Best Response (A-BR)
procedureA-BR(configuration p, error ɛ)
Initialize v^A (s) ←0 for all $s \in S$
do
${\tilde{v}}^{A} \leftarrow v^{A}$
$v^{A} \leftarrow B_{*, p}^{A}$
while ${∥ v^{A} - {\tilde{v}}^{A} ∥}_{\infty} > ɛ$
returnv^A
end procedure

Algorithm 3. Configurator Best Response (C-BR)
procedureC-BR(policy π, error ɛ)
Initialize q^C (s, a) ←0 for all $(s, a) \in S \times A$
do
${\tilde{q}}^{C} \leftarrow q^{C}$
$q^{C} \leftarrow B_{π, *}^{C}$
while ${∥ q^{C} - {\tilde{q}}^{C} ∥}_{\infty} > ɛ$
returnq^C
end procedure

7 Cooperative Conf-MDPs

In this section, we focus on the cooperative setting characterized by the fact that the agent and the configurator share the same objectives. In such a case, we can consider a unique reward function r and we speak of cooperative Conf-MDPs.

Definition 7.1. (Cooperative Conf-MDP). Let $C = (S, A, r^{A}, r^{C}, γ)$ be a Conf-MDP. $C$ is a Cooperative Conf-MDP if for every state-action-next-state triple $(s, a, s^{'}) \in S \times A \times S$ it holds that: $r^{A} (s, a, s^{'}) = r^{C} (s, a, s^{'}) .$ (5) In this case, we abbreviate r : = r^A = r^C.

Moreover, we will remove the superscripts A and C from the value functions and from the operators. The goal in a cooperative Conf-MDP can be stated as determining a policy and a configuration such that they jointly optimize the expected discounted sum of the rewards. As there is no competition between agent and configurator, it is straightforward to define a solution concept for this setting. The following definition formalizes intuition.

Definition 7.2. (Optimal Value Functions). The agent optimal value function $υ_{*, *} \in ℝ^{S}$ is defined for all states $s \in S$ as: $\begin{matrix} υ_{*, *} (s) & = sup_{π \in Δ_{S}^{A}, p \in Δ_{S \times A}^{S}} {υ_{π, p}^{A} (s)} . \end{matrix}$ The configurator optimal value function $q_{*, *} \in ℝ^{S \times A}$ is defined for all state-action pairs $(s, a) \in S \times A$ as: $\begin{matrix} q_{*, *} (s, a) & = sup_{π \in Δ_{S}^{A}, p \in Δ_{S \times A}^{S}} {q_{π, p} (s, a)} . \end{matrix}$

We observe, given the identity of the reward functions it holds that $υ_{*, *} (s) = max_{a \in A} {q_{*, *} (s, a)}$ for all $s \in S$ . Moreover, we say that a policy-configuration pair $(π^{*}, p^{*}) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ is optimal if it fulfills the following condition for all $(s, a) \in S \times A$ : $\begin{matrix} υ_{π^{*}, p^{*}} (s) = υ_{*, *} (s), q_{π^{*}, p^{*}} (s, a) = q_{*, *} (s, a), \end{matrix}$ that is, if it attains the optimal value functions.

7.1 Existence of optimal policy-configuration Pairs

Similarly to the case of best responses, we wonder whether the optimal policy-configuration pairs actually exist. For this purpose, we provide the following reduction showing that determining the optimal pair (π^*, p^*) in a cooperative Conf-MDP is indeed equivalent to solving a suitably defined deterministic MDP.

Theorem 7.1. Let $C = (S, A, r, γ)$ be a cooperative Conf-MDP and let $\tilde{M} = (S, A \times S, \tilde{p}, \tilde{r}, γ)$ be an MDP defined as follows:

$\tilde{p} : S \times (A \times S) \to Δ^{S}$ , defined for every $(s, (a, s^{'})) \in S \times (A \times S)$ and $s^{″} \in S$ as:

$\tilde{r} : S \times (A \times S) \times S \to ℝ$ , defined for $(s, (a, s^{'}), s^{″}) \in S \times (A \times S) \times S$ as: $\tilde{r} (s, (a, s^{'}), s^{″}) = r (s, a, s^{'}) .$

Then, for every $(π, p) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ define the policy $\tilde{π} : S \to Δ^{A \times S}$ for the MDP $\tilde{M}$ for every $(a, s^{'}) \in A \times S$ as:

\tilde{π} ((a, s^{'}) | s) = π (a | s) p (s^{'} | s, a) .

Then, for every state-action pair $(s, a) \in S \times A$ it holds that:

\begin{matrix} υ_{π, p}^{C} (s) = υ_{\tilde{π}}^{\tilde{M}} (s), q_{π, p}^{C} (s, a) = q_{\tilde{π}}^{\tilde{M}} (s, a) . \end{matrix}

Proof: It is sufficient to prove the Bellman operator associated to the policy-configuration pair $(π, p) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ in the cooperative Conf-MDP $C$ , i.e., $B_{π, p}^{C, C}$ equals the Bellman operator associated to $\tilde{π}$ in the MDP $\tilde{M}$ , i.e., $B_{\tilde{π}}^{\tilde{M}}$ . Let $f \in ℝ^{S}$ and let $s \in S$ :

The proof for the operator of the configurator value function is analogous. □

Thus, thanks to the reduction, we can compute the optimal policy-configuration pair (π^*, p^*) as the greedy pair w.r.t the corresponding optimal value functions as done in Equations (1) and (2). Moreover, one deterministic optimal pair exists.

7.2 Optimal Bellman operator for cooperative Conf-MDPs

We now introduce the optimal Bellamn operator for cooperative Conf-MDPs and provide the analysis of its properties.

Definition 7.3. (Optimal Bellman Operator for Cooperative Conf-MDPs). The optimal Bellman operator for the state value function $B_{*, *} : R^{S} \to R^{S}$ is defined for every function $f \in ℝ^{S}$ and every state $s \in S$ as: $\begin{matrix} B_{*, *} [f] (s) & = max_{a \in A, s^{'} \in S} {r (s, a, s^{'}) + γ f (s^{'})} \\ = (M_{S} ((M_{A} r) (s, \cdot) + γ f)) (s) . \end{matrix}$ The optimal Bellman operator for the action value function $B_{*, *} : R^{S \times A} \to R^{S \times A}$ is defined for every function $g \in ℝ^{S \times A}$ and every state-action pair $(s, a) \in S \times A$ as: $\begin{matrix} B_{*, *} [g] (s, a) & = max_{s^{'} \in S} {r (s, a, s^{'}) + γ max_{a^{'} \in A} {g (s^{'}, a^{'})}} \\ = (M_{S} (r (s, a, \cdot) + γ M_{A} g)) (s, a) . \end{matrix}$

It is immediate to prove that these operators are γ-contractions in L_∞-norm and, consequently, they admit a unique fixed point, represented by the optimal value functions.

Proposition 7.2. The Bellman optimal operators $B_{*, *}$ are γ-contractions in L_∞-norm, i.e., for all $f, f^{'} \in ℝ^{S}$ and $g, g^{'} \in ℝ^{S \times A}$ : $\begin{matrix} {∥ B_{*, *} [f] - B_{*, *} [f^{'}] ∥}_{\infty} \leq γ {∥ f - f^{'} ∥}_{\infty}, \\ {∥ B_{*, *} [g] - B_{*, *} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ Moreover, the optimal value functions υ_*,* and q_*,* are their unique fixed points respectively: $\begin{matrix} υ_{*, *} = B_{*, *} [υ_{*, *}], q_{*, *} = B_{*, *} [q_{*, *}] . \end{matrix}$

Proof. We prove the result for the first operator, as the derivation for the second is equivalent: $\begin{matrix} B_{*, *} [f] - B_{*, *} [f^{'}] \\ = M_{S} ((M_{A} r) (_, \cdot) + γ f) - M_{S} ((M_{A} r) (_, \cdot) + γ f^{'}) \\ \leq M_{S} | (M_{A} r) (_, \cdot) + γ f - M_{S} - (M_{A} r) (_, \cdot) + γ f^{'} | \\ = γ M_{S} | f - f^{'} | \\ = γ {∥ f - f^{'} ∥}_{\infty}, \end{matrix}$ where we denoted with (_ , ·) the fact that the operator is applied to the second argument only. By taking the L_∞-norm, we have: $\begin{matrix} {∥ B_{*, *} [f] - B_{*, *} [f^{'}] ∥}_{\infty} & \leq γ {∥ f - f^{'} ∥}_{\infty} . \end{matrix}$ Thus, we can extend the last part of the proof of Proposition 6.2 to deduce that $B_{*, *}$ admits a unique fixed point that corresponds to υ_*,*. □

7.3 Optimal value function computation

The computation of such optimal value functions can be derived by exploiting an iterative procedure, like the one in Algorithm 4. This algorithm inherits all the properties derived in Theorem 5.2. It is worth noting that in the cooperative setting the reward functions are the same for the agent and the configuration, it is sufficient to compute one of the value functions, say q_*,*, and then derive the other v_*,*.

Algorithm 4. Agent Configurator Cooperative
Optimization (A-C-CO)
procedureA-C-CO(error ɛ)
Initialize q (s, a) ←0 for all $(s, a) \in S \times A$
do
$\tilde{q} \leftarrow q$
$q \leftarrow B_{, }$
while ${∥ v - \tilde{v} ∥}_{\infty} > ɛ$
$v \leftarrow M_{A} q$
returnv, q
end procedure

8 Non-cooperative Conf-MDPs

In this section, we introduce the setting of non-cooperative Conf-MDPs, i.e., the case in which agent and configurator might have diverging interests, modeled by possibly different reward functions r^A ≠ r^C. While the cooperative setting has been diffusely addressed, the non-cooperative one is less studied [39].

In order to properly address the setting, we distinguish two types of interactions between the agent and the configurator, leading to different suitable solution concepts:

Turn-based Conf-MDPs: the interaction is carried out in steps. At every step, the agent selects the action $a \in A$ and the configurator, having observed the action, selects the next state $s^{'} \in S$ .

Leader-Follower Conf-MDPs: the configurator commits to a configuration $p \in Δ_{S \times A}^{S}$ at the beginning of the interaction, while the agent then selects the policy $π \in Δ_{S}^{A}$ to be played.

Other kinds of interactions might be inappropriate for the Conf-MDP setting. For instance, the simultaneous selection of the action by the agent

a \in A

and of the next state

s^{'} \in S

by the configurator, based on the current state

s \in S

only, is unrealistic as the configurator usually has access to the agent’s action. We will dive into the details of the non cooperative setting in the next sections.

9 Turn-based Conf-MDPs

In turn-based Conf-MDPs, at each step $t \in ℕ$ , the agent observes the state of the environment $s_{t} \in S$ and selects the action to be played $a_{t} \in A$ based on its policy π (· |s_t). Then, the configurator, observing the state $s_{t} \in S$ and the action a_t, chooses the next state s_t+1 according to the transition model p (· |s_t, a_t). In this setting, it is reasonable to consider the Nash equilibrium [32] a suitable solution concept, that we adapt for Conf-MDPs.

Definition 9.1. (Nash Equilibrium in Conf-MDPs). A policy $π^{*} \in Δ_{S}^{A}$ and a configuration $p^{*} \in Δ_{S \times A}^{S}$ are a Nash equilibrium for the Conf-MDP if the following two conditions hold for every state-action pair $(s, a) \in S \times A$ : $\begin{matrix} υ_{π^{*}, p^{*}}^{A} (s) = υ_{*, p^{*}}^{A} (s), \\ q_{π^{*}, p^{*}}^{C} (s, a) = q_{π^{*}, *}^{C} (s) . \end{matrix}$

Thus, a pair $(π^{*}, p^{*}) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ is a Nash equilibrium of the Conf-MDP if the value functions υ_π^*,p^* and q_π^*,p^* for the agent and the configurator are equal to the corresponding best response value functions υ_*,p^* and q_π^*,*, respectively. This means that neither the agent nor the configurator has a unilateral interest in deviating from the equilibrium.

9.1 Existence of the Nash equilibrium for Conf-MDPs

A legit question is whether the Nash equilibrium as in Definition 9.1 does exist. In order to show the existence of a Nash equilibrium for the turn-based Conf-MDPs, we provide the following reduction to a turn-based Markov Game for which a Nash equilibrium is known to exist [4, 44].

Theorem 9.1. Let $C = (S, A, r^{A}, r^{C}, γ)$ be a turn-based Conf-MDP and let $\tilde{G}$ = $(S$ , $S$ × $A$ , $A$ , $S$ , $\tilde{p}$ , ${\tilde{r}}^{A}$ , ${\tilde{r}}^{C}$ , $\sqrt{γ})$ be an alternated turn-based MG, defined as follows, where $\tilde{S} : = S \cup (S \times A)$ and $\tilde{A} : = A \cup S$ :

$\tilde{p} : \tilde{S} \times \tilde{A} \to Δ^{\tilde{S}}$ , defined for every $(\tilde{s}, \tilde{a}) \in \tilde{S} \times \tilde{A}$ and ${\tilde{s}}^{'} \in \tilde{S}$ as: where the symbol ⊥ denotes undefined;

${\tilde{r}}_{1}, {\tilde{r}}_{2} : \tilde{S} \times \tilde{A} \times \tilde{S} \to ℝ$ , defined for $(\tilde{s}, \tilde{a}, {\tilde{s}}^{'}) \in \tilde{S} \times \tilde{A} \times \tilde{S}$ as: $\begin{matrix} {\tilde{r}}^{A} (\tilde{s}, \tilde{a}, {\tilde{s}}^{'}) = {\begin{matrix} \frac{1}{\sqrt{γ}} r^{A} (s, a, {\tilde{s}}^{'}) & if \tilde{s} = (s, a) \in S \times A \land \\ \tilde{a} \in S \land {\tilde{s}}^{'} \in S \\ 0 & otherwise \end{matrix}, \\ {\tilde{r}}^{C} (\tilde{s}, \tilde{a}, {\tilde{s}}^{'}) = {\begin{matrix} r^{C} (s, a, {\tilde{s}}^{'}) & if \tilde{s} = (s, a) \in S \times A \land \\ \tilde{a} \in S \land {\tilde{s}}^{'} \in S \\ 0 & otherwise \end{matrix} . \end{matrix}$

Then, for every $(π, p) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ define the policies ${\tilde{π}}^{A}, {\tilde{π}}^{C} : \tilde{S} \to Δ^{\tilde{A}}$ for the turn-based MG $\tilde{G}$ for every $\tilde{s} \in \tilde{S}$ as:

\begin{matrix} {\tilde{π}}^{A} (\tilde{a} | \tilde{s}) = {\begin{matrix} π (\tilde{a} | \tilde{s}) & if \tilde{s} \in S, \tilde{a} \in A \\ 0 & if \tilde{s} \in S, \tilde{a} \notin A \\ ⊥ & otherwise \end{matrix}, \\ {\tilde{π}}^{C} (\tilde{a} | \tilde{s}) = {\begin{matrix} p (\tilde{a} | s, a) & if \tilde{s} = (s, a) \in S \times A, \tilde{a} \in S \\ 0 & if \tilde{s} \in S \times A, \tilde{a} \notin S \\ ⊥ & otherwise \end{matrix} . \end{matrix}

Then, for every state-action pair $\tilde{s} \in \tilde{S}$ it holds that:

\begin{matrix} υ_{π, p}^{\tilde{G}, A} (\tilde{s}) = υ_{π, p}^{C, A} (\tilde{s}) if \tilde{s} \in S, \\ υ_{π, p}^{\tilde{G}, C} (\tilde{s}) = q_{π, p}^{C, C} (s, a) if \tilde{s} = (s, a) \in S \times A . \end{matrix}

Before moving to the proof, it is worth commenting the above construction. First of all, we observe that the game is deterministic. Moreover, the rationale is to construct a turn-based MG in which agent and configurator alternate in playing, with the agent selecting an action and the configurator the next state. In particular, the reward is given to the agent and to the configurator at the end of two steps, when the configurator has played. This is why the reward function ${\tilde{r}}^{A}$ is corrected by the factor $1 / \sqrt{γ}$ .

Proof: We prove that the Bellman operators associated to $(π, p) \in Δ_{S}^{A} \times Δ_{S \times A}^{S}$ in the Conf-MDP $C$ , i.e., $B_{π, p}^{C, A}$ and $B_{π, p}^{C, C}$ , equal the Bellman operators associated to policies ${\tilde{π}}^{A}$ and ${\tilde{π}}^{C}$ in the MG $\tilde{G}$ , i.e., $B_{{\tilde{π}}^{A}, {\tilde{π}}^{C}}^{\tilde{G}, A}$ and $B_{{\tilde{π}}^{A}, {\tilde{π}}^{C}}^{\tilde{G}, C}$ . We limit the derivation for the agent case, as for the configurator the steps are analogous. Let $f \in ℝ^{S}$ and $s \in S$ :

□

Being the turn-based Conf-MDP isomorphic to the turn-based Markov Game, we can immediately conclude the existence of the Nash equilibrium in (possibly) mixed strategies (i.e., stochastic policies) [4, 44]. We now focus on a particular case of interest represented by the zero-sum Conf-MDPs.

10 Zero-sum Conf-MDPs

In this section, we consider the case in which agent and configurator demonstrate fully competitive interests. We refer to this setting to as zero-sum Conf-MDPs, that are formalized in the following definition.

Definition 10.1. (Zero-Sum Conf-MDP). Let $C = (S, A, r^{A}, r^{C}, γ)$ be a Conf-MDP. $C$ is a Zero-Sum Conf-MDP if for every state-action-next-state triple $(s, a, s^{'}) \in S \times A \times S$ it holds that: $r^{A} (s, a, s^{'}) + r^{C} (s, a, s^{'}) = 0 .$ (6) In such a case, we denote with r : = r^A = - r^C.

Thus, looking at the problem as a zero-sum game, the agent seeks to maximize the reward r, while the configurator aims at minimizing it, i.e., we are in a fully competitive setting.

10.1.1 Minimax value functions

Similarly to what done in the previous scenarios, we introduce the minimax value functions, that can be defined based on the Von Neumann minimax theorem [45].

Definition 10.2. (Minimax Value Functions). The agent minimax value function $υ_{\max, \min}^{A} \in ℝ^{S}$ is defined for all states $s \in S$ as: $\begin{matrix} υ_{\max, \min}^{A} (s) & = sup_{π \in Δ_{S}^{A}} inf_{p \in Δ_{S \times A}^{S}} {υ_{π, p}^{A} (s)} . \end{matrix}$ The configurator minimax value function $q_{\min, \max}^{C} \in ℝ^{S \times A}$ is defined for all state-action pairs $(s, a) \in S \times A$ as: $\begin{matrix} q_{\min, \max}^{C} (s, a) & = sup_{p \in Δ_{S \times A}^{S}} inf_{π \in Δ_{S \times A}^{S}} {q_{π, p}^{C} (s, a)} . \end{matrix}$

It is worth noting that, thanks to the reduction of Theorem 9.1, we are in presence of an interaction that can be modeled as a turn-based MG. In particular, it is well-known that for zero-sum turn-based MG the Nash equilibrium exists in pure strategies (i.e., deterministic polices) [3 , 35]. Thus, we can restrict our attention to the deterministic policies and configurations. Once we have to compute the minimax value functions, the equilibrium policy and configuration can be computed by the greedyfication operation as in Equations (1) and (2).

10.1.2 Bellman minimax operators

We now proceed at introducing the Bellman minimax operators for the case of zero-sum Conf-MDPs.

Definition 10.3. (Bellman Minimax Operators). The agent Bellman minimax operator $B_{\max, \min}^{A} : R^{S} \to R^{S}$ is defined for all $f \in ℝ^{S}$ as for all states $s \in S$ : $\begin{matrix} B_{\max, \min}^{A} [f] (s) = sup_{π \in Δ_{S}^{A}} inf_{p \in Δ_{S \times A}^{S}} {(r_{π, p}^{A} + γ Π Pf) (s)} \\ = sup_{π \in Δ_{S}^{A}} inf_{p \in Δ_{S \times A}^{S}} {r_{π, p}^{A} (s) + γ \sum_{a \in A} π (a | s) \\ \times \sum_{s^{'} \in S} p (s^{'} | s, a) f (s^{'})} . \end{matrix}$ The configurator Bellman minimax operator $B_{\min, \max}^{C} : R^{S \times A} \to R^{S \times A}$ to configuration p is defined for all agent value functions $g \in ℝ^{S}$ as for all states $s \in S$ : $\begin{matrix} B_{\min, \max}^{C} [g] (s, a) = sup_{p \in Δ_{S \times A}^{S}} inf_{π \in Δ_{S}^{A}} {(r_{p}^{C} + γ P Π g) (s, a)} \\ = sup_{p \in Δ_{S \times A}^{S}} inf_{π \in Δ_{S}^{A}} {r_{p}^{C} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) \\ \times \sum_{a^{'} \in A} π (a^{'} | s^{'}) g (s^{'}, a^{'})} . \end{matrix}$ We now prove that such operators are a γ-contractions and admit the minimax value function as corresponding fixed points.

Proposition 10.1. The minimax Bellman operators $B_{\max, \min}^{A}$ and $B_{\min, \max}^{C}$ are γ-contractions in L_∞-norm, i.e., for all $f, f^{'} \in ℝ^{S}$ and $g, g^{'} \in ℝ^{S \times A}$ : $\begin{matrix} {∥ B_{\max, \min}^{A} [f] - B_{\max, \min}^{A} [f^{'}] ∥}_{\infty} \leq γ {∥ f - f^{'} ∥}_{\infty}, \\ {∥ B_{\min, \max}^{C} [g] - B_{\min, \max}^{C} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ Moreover, the agent minimax value function $υ_{\max, \min}^{A}$ and the configurator minimax value function $q_{\min, \max}^{C}$ are their unique fixed points respectively: $\begin{matrix} υ_{\max, \min}^{A} = B_{\max, \min}^{A} [υ_{\max, \min}^{A}], \\ q_{\min, \max}^{C} = B_{\min, \max}^{C} [q_{\min, \max}^{C}] . \end{matrix}$

Proof: We prove the contraction property for the first operator, as the proof for the second is fully analogous: $\begin{matrix} B_{\max, \min}^{A} [f] - B_{\max, \min}^{A} [f^{'}] \\ = sup_{π \in Δ_{S}^{A}} inf_{p \in Δ_{S \times A}^{S}} {r_{π, p}^{A} + γ Π Pf} \\ - sup_{π \in Δ_{S}^{A}} inf_{p \in Δ_{S \times A}^{S}} {r_{π, p}^{A} + γ Π P f^{'}} \\ \leq sup_{π \in Δ_{S}^{A}} {| inf_{p \in Δ_{S \times A}^{S}} {r_{π, p}^{A} + γ Π Pf} \\ - inf_{p \in Δ_{S \times A}^{S}} {r_{π, p}^{A} + γ Π Pf} |} \\ \leq γ sup_{π \in Δ_{S}^{A}} sup_{p \in Δ_{S \times A}^{S}} {| Π P (f - f^{'}) |} \\ \leq γ {∥ f - f^{'} ∥}_{\infty}, \end{matrix}$ where we exploited the fact that for generic functions h and h′, we have: $\begin{matrix} | inf_{x \in X} {h (x)} - inf_{x \in X} {h^{'} (x)} | \leq sup_{x \in X} {| h (x) - h^{'} (x) |} . \end{matrix}$ By applying the L_∞-norm, we have: $\begin{matrix} {∥ B_{\max, \min}^{A} [f] - B_{\max, \min}^{A} [f^{'}] ∥}_{\infty} \leq γ {∥ f - f^{'} ∥}_{\infty} . \end{matrix}$ To prove that the minimax value function is the unique fixed point, we can apply an argument analogous to that of Theorem 6.1. □

10.1.3 Minimax value function computation

Before showing the algorithm able to compute the minimax value functions via an iterative procedure, it is worth noting that since the Nash equilibrium exists in pure strategies (i.e., deterministic policy and configuration), we can simplify the application of the Bellman minimax operators, by replacing the optimization of the space of stochastic policies $Δ_{S}^{A}$ and transition models $Δ_{S \times A}^{S}$ with the optimization over the deterministic actions $A$ and deterministic next states $S$ . This observation leads to the following simplified operators defined for $f \in ℝ^{S}$ , $g \in ℝ^{S \times A}$ and $S \times A a$ : $\begin{matrix} B_{\max, \min}^{A} [f] (s) = max_{a \in A} min_{s^{'} \in S} {r^{A} (s, a, s^{'}) + γ f (s^{'})}, \\ B_{\min, \max}^{C} [g] (s, a) \\ = max_{s^{'} \in S} min_{a^{'} \in A} {(r^{C} (s, a, s^{'}) + γ g (s^{'}, a^{'})) (s, a)} . \end{matrix}$ Algorithm 5 reports the pseudocode of the iterative procedure consisting in the repeated application of these operators until ɛ-convergence. This algorithm preserves the guarantees of Theorem 5.2 thanks to the properties of the minimax Bellman operators. Concerning the computational complexity, it is worth noting that the application of the operators, in the form reported right above, requires, in the worst case, enumerating all state-action pairs for the minimax, leading to the same complexity as in Theorem 5.2.

Algorithm 5. Agent Configurator Minimax
Optimization (A-C-MMO)
procedureA-C-MMO(error ɛ)
Initialize v^A (s) ←0 for all $s \in S$
Initialize q^C (s, a) ←0 for all $(s, a) \in S \times A$
do
${\tilde{v}}^{A} \leftarrow v^{A}$
${\tilde{q}}^{C} \leftarrow q^{C}$
$v^{A} \leftarrow B_{\max, \min}^{A}$
$q^{C} \leftarrow B_{\min, \max}^{A} [{\tilde{q}}^{C}]$
while ${∥ v^{A} - {\tilde{v}}^{A} ∥}_{\infty} > ɛ$ or ${∥ q^{C} - {\tilde{q}}^{C} ∥}_{\infty} > ɛ$
returnv^A, q^C
end procedure

11 Leader-follower Conf-MDPs

In the leader-follower setting, instead, the configurator selects a transition model $p \in Δ_{S \times A}^{S}$ and commits to it. Subsequently, the configurator selects a policy $π \in Δ_{S \times A}^{S}$ to be used for the interaction [39]. This setting resembles the leader-follower game in which the leader is represented by the configurator and the follower by the agent. Under the assumption that the agent reacts to a configuration p with one of its best response policies, i.e., it acts as a best responder, the Stackelberg equilibrium is a suitable solution concept for this setting [6, 45].

Definition 11.1. (Stackelberg Equilibrium in Conf-MDPs). Let $β^{A} : Δ_{S \times A}^{S} \to Δ_{S}^{A}$ be a choice function in the set of agent best response policies, i.e., for every configuration $p \in Δ_{S \times A}^{S}$ it holds that β^A (p) ∈ BR^A (p). A policy $π^{*} \in Δ_{S}^{A}$ and a configuration $p^{*} \in Δ_{S \times A}^{S}$ are a β^A-Stackelberg equilibrium for the Conf-MDP if the following two conditions hold for every state-action pair $(s, a) \in S \times A$ : $\begin{matrix} π^{*} = β^{A} (p^{*}), \\ q_{β^{A} (p^{*}), p^{*}} (s, a) = sup_{p \in Δ_{S \times A}^{S}} {q_{β^{A} (p), p} (s, a)} . \end{matrix}$ Furthermore, we define the β^A-Stackelberg value function for every state-action pair $(s, a) \in S \times A$ as: $\begin{matrix} q_{β^{A} (*), *} (s, a) : = sup_{p \in Δ_{S \times A}^{S}} q_{β^{A} (p), p} (s, a) \end{matrix}$

Thus, the definition of Stackelberg equilibrium depends on the choice function β^A, leading to different instances of the equilibrium. In particular, if ties are broken in favor of the leader (i.e., the configurator), we speak of strong Stackelberg equilibrium, whereas if ties are broken in favor of the follower (i.e., the agent), we refer to a weak Stackelberg equilibrium. Unfortunately, we are currently unable to show the existence of such a class of equilibria and whether they are actually attained, in Conf-MDPs, with Markovian policies or configurations [46]. Nevertheless, we can introduce suitable extensions of the Bellman operators.

11.1.1 β^A-Stackelberg Bellman Operator

Similarly to the previous settings, we introduce a suitable operator for the computation of the β^A-Stackelberg value function.

Definition 11.2. (β^A-Stackelberg Bellman Operator). Let $β^{A} : Δ_{S \times A}^{S} \to Δ_{S}^{A}$ be a choice function in the set of agent best response policies, i.e., for every configuration $p \in Δ_{S \times A}^{S}$ it holds that β^A (p) ∈ BR^A (p). The β^A-Stackelberg Bellman Operator $B_{β^{A} (*), *}^{C} : R^{S \times A} \to R^{S \times A}$ is defined for all $g \in ℝ^{S \times A}$ for all state-action pairs $(s, a) \in S \times A$ as: $\begin{matrix} B_{β^{A} (*), *}^{C} [g] (s, a) = sup_{p \in Δ_{S \times A}^{S}} {(r_{p} + γ P (B^{A} (p)) g) (s, a)} \\ = sup_{p \in Δ_{S \times A}^{S}} {r_{p}^{C} (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) \\ \times \sum_{a^{'} \in A} (β^{A} (p)) (a | s) g (s^{'}, a^{'})}, \end{matrix}$ where B^A (p) is the operator induced by policy β^A (p).

It is simple to prove that such an operator is contraction and its fixed point is represented by the β^A-Stackelberg value function.

Proposition 11.1. The β^A-Stackelberg Bellman operator $B_{β^{A} (*), *}^{C}$ is a γ-contractions in L_∞-norm, i.e., for all $g, g^{'} \in ℝ^{S \times A}$ : $\begin{matrix} {∥ B_{β^{A} (*), *}^{C} [g] - B_{β^{A} (*), *}^{C} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ Moreover, the β^A-Stackelberg value function q_β^A(*),* is its unique fixed point: $\begin{matrix} q_{β^{A} (*), *} = B_{β^{A} (*), *}^{C} [q_{β^{A} (*), *}] . \end{matrix}$

Proof: We limit to prove that the operator is a γ-contraction, the existence and the value of the fixed point can be proved analogously to Proposition 6.2: $\begin{matrix} B_{β^{A} (*), *}^{C} [g] - B_{β^{A} (*), *}^{C} [g^{'}] \\ = sup_{p \in Δ_{S \times A}^{S}} {(r_{p} + γ P (B^{A} (p)) g)} \\ - sup_{p \in Δ_{S \times A}^{S}} {(r_{p} + γ P (B^{A} (p)) g^{'})} \\ \leq sup_{p \in Δ_{S \times A}^{S}} {| r_{p} + γ P (B^{A} (p)) g - r_{p} - γ P (B^{A} (p)) g^{'} |} \\ = γ sup_{p \in Δ_{S \times A}^{S}} {P (B^{A} (p)) | g - g^{'} |} \\ \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ By taking the L_∞-norm, we obtain: $\begin{matrix} {∥ B_{β^{A} (*), *}^{C} [g] - B_{β^{A} (*), *}^{C} [g^{'}] ∥}_{\infty} \leq γ {∥ g - g^{'} ∥}_{\infty} . \end{matrix}$ □

11.1.2 Computation of the β^A-Stackelberg value function

We now provide an algorithm for the iterative computation of the β^A-Stackelberg value function, under the assumption that we can computationally evaluate the choice function β^A (Algorithm 6). The convergence guarantees of this algorithm are analogous to those provided in Theorem 5.2. Unfortunately, the computational complexity depends on the evaluation of the β^A, in principle, for every candidate transition model p.

Algorithm 6. Configurator Stackelberg Optimization (C-SO)
procedureC-SO(choice function β^A, error ɛ)
Initialize q^C (s, a) ←0 for all $(s, a) \in S \times A$
do
${\tilde{q}}^{C} \leftarrow q^{C}$
$q^{C} \leftarrow B_{β^{A} (), }^{C}$
while ${∥ q^{C} - {\tilde{q}}^{C} ∥}_{\infty} > ɛ$
returnq^C
end procedure

12 Discussion and conclusions

In this paper, we have provided a unified view of the configurable MDP framework. We have shown how the cooperative and non-cooperative settings can be modeled, how to extend the traditional value functions, and Bellman operators to these settings, and how to exploit them to compute iteratively those value functions. Relevant results have been provided regarding the reduction of the computation of the best response value function and the solution of the cooperative Conf-MDP to the solution of a traditional MDP. Furthermore, we have provided a reduction of the turn-based non-cooperative Conf-MDP to an alternated turn-based MG. This allowed us to exploit the available result regarding the existence of the Nash-equilibrium. Finally, the leader-follower formulation, although of interest for real-world application, requires additional attention and study to understand its properties in terms of equilibria existence and efficient computation of the value functions. Overall, the degree of development of the environment configuration research line displays a mature study of the cooperative setting, justified by its intrinsic simplicity and existence of intuitive solutions. Instead, the non-cooperative setting deserves further analysis.

Clearly, being a recent research line, Conf-MDPs offer numerous research opportunities, including the adaptation of model-based approaches [8, 47] and off-policy/off-distribution methods [29, 36]. A completely disregarded topic in the environment configuration area is the problem of effective exploration of the configuration space [1]. Previous approaches designed for standard RL could be adapted to the Conf-MDP setting [20, 24]. Furthermore, Conf-MDPs could be applied to inverse reinforcement learning [27 , 51], i.e., the process of recovering a reward function by observing the demonstrations of an expert agent. Similarly to policy space identification, configuring the environment can induce the expert agent to reveal its intent, helping the reward reconstruction process.

Footnotes

Formally, it must be that $(s, a) \in (S_{1} \times A_{1}) \cup (S_{2} \cup A_{2})$ .

The study of the effects of considering non-Markovian policies and configurations in the Conf-MDP setting is beyond the scope of the present work.

References

Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer, Finite-time analysis of the multiarmed bandit problem, Mach. Learn. 47(2-3) (2002), 235–256.

Richard Bellman, The theory of dynamic programming, Bulletin of the American Mathematical Society 60(6) (1954), 503–515.

A. Bensoussan and J. Frehse, Stochastic games for n players, Journal of Optimization Theory and Applications 105(3) (2000), 543–565.

Krishnendu Chatterjee, Rupak Majumdar and Marcin Jurdzinski, On Nash Equilibria in Stochastic Games. In Computer Science Logic, 18th International Workshop (CSL), pages 26–40, 2004.

Kamil Andrzej Ciosek and Shimon Whiteson, OFFER: off-environment reinforcement learning, In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI), pages 1819–1825, AAAI Press, 2017.

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.

Yue Deng, Feng Bao, Youyong Kong, Zhiquan Ren and Qionghai Dai, Deep direct reinforcement learning for financial signal representation and trading, IEEE Trans. Neural Networks Learn. Syst. 28(3) (2017), 653–664.

Pierluca D’Oro, Alberto Maria Metelli, Andrea Tirinzoni, Matteo Papini and Marcello Restelli, Gradient-aware model-based policy search, In The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), pages 3801–3808, AAAI Press, 2020.

Zehao Dou, Zhuoran Yang, Zhaoran Wang and Simon S. Du, Gap-dependent bounds for two-player markov games, CoRR, abs/2107.00685, 2021.

10.

Tuomas Haarnoja, Sehoon Ha, Aurick Zhou, Jie Tan, George Tucker and Sergey Levine, Learning to walk via deep reinforcement learning, In Robotics: Science and Systems XV, University of Freiburg, 2019.

11.

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-Sixth International Joint Conference on Artificial Intelligence (IJCAI), pages 4353–4360. ijcai.org, 2017.

12.

Erwan Lecarpentier and Emmanuel Rachelson, Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019)), pages 7214–7223, 2019.

13.

Boris Lesner and Bruno Scherrer, Non-stationary approximate modified policy iteration, In Proceedings of the 32nd International Conference on Machine Learning (ICML)), volume 37, pages 1567–1575. JMLR.org, 2015..

14.

Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, Riccardo Giol, Marcello Restelli and Danilo Romano, Combining reinforcement learning with rule-based controllers for transparent and general decision-making in autonomous driving, Robotics and Autonomous Systems 131 (2020), 103568.

15.

Littman Michael

, Markov games as a framework for multi-agent reinforcement learning, In Proceedings of the Eleventh International Conference (ICML)), pages 157–163. Morgan Kaufmann, 1994.

16.

Yuzhe Ma, Xuezhou Zhang, Wen Sun and Jerry Zhu, Policy poisoning in batch reinforcement learning and control, In Advances in Neural Information Processing Systems 32 (NeurIPS)), pages 14543–14553, 2019.

17.

Alberto Maria Metelli, Exploiting environment configurability in reinforcement learning, PhD thesis, Politecnico di Milano, March 2021.

18.

Alberto Maria Metelli, Configurable environments in reinforcement learning: An overview, In Luigi Piroddi, editor, Special Topics in Information Technology, pages 101–113, Cham, 2022. Springer International Publishing.

19.

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, pages 4546–4555. PMLR, 2019.

20.

Alberto Maria Metelli, Amarildo Likmeta and Marcello Restelli, Propagating uncertainty in reinforcement learning via wasserstein barycenters, In Advances in Neural Information Processing Systems 32 (NeurIPS)), pages 4335–4347, 2019.

21.

Alberto Maria Metelli, Guglielmo Manneschi and Marcello Restelli, Policy space identification in configurable environments, Machine Learning 111(6) (2022), 2093–2145.

22.

Alberto Maria Metelli, Flavio Mazzolini, Lorenzo Bisi, Luca Sabbioni and Marcello Restelli, Control frequency adaptation via action persistence in batch reinforcement learning, In Proceedings of the 37th International Conference on Machine Learning (ICML)), volume 119, pages 6862–6873. PMLR, 2020.

23.

Alberto Maria Metelli, Mirco Mutti and Marcello Restelli, Configurable Markov decision processes, In Proceedings of the 35th International Conference on Machine Learning (ICML)), volume 80, pages 3488–3497. PMLR, 2018.

24.

Alberto Maria Metelli, Matteo Papini, Pierluca D’Oro and Marcello Restelli, Policy optimization as online learning with mediator feedback, In The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pages 8958–8966. AAAI Press, 2021.

25.

Alberto Maria Metelli, Matteo Papini, Francesco Faccio and Marcello Restelli, Policy optimization via importance sampling, In Advances in Neural Information Processing Systems 31 (NeurIPS)), pages 5447–5459, 2018.

26.

Alberto Maria Metelli, Matteo Papini, Nico Montali and Marcello Restelli, Importance sampling techniques for policy optimization, Journal of Machine Learning Research 21(141) (2020), 1–75.

27.

Alberto Maria Metelli, Matteo Pirotta and Marcello Restelli, On the use of the policy gradient and hessian in inverse reinforcement learning, Intelligenza Artificiale 14(1) (2020), 91–124.

28.

Alberto Maria Metelli, Giorgia Ramponi, Alessandro Concetti and Marcello Restelli, Provably efficient learning of transferable rewards, In Proceedings of the 38th International Conference on Machine Learning (ICML) ), volume 139, pages 7665–7676. PMLR, 2021.

29.

Alberto Maria Metelli, Alessio Russo and Marcello Restelli, Subgaussian and differentiable importance sampling for off-policy evaluation and learning, In Advances in Neural Information Processing Systems 34 (NeurIPS). 2021.

30.

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg and Demis Hassabis, Human-level control through deep reinforcement learning, Nat. 518(7540) (2015), 529–533.

31.

Rémi Munos, Performance bounds in l_p-norm for approximate value iteration, SIAM J. Control. Optim. 46(2) (2007), 541–561.

32.

John Nash, Non-cooperative games, Annals of Mathematics 54(2) (1951), 286–295.

33.

Andrew Y. Ng and Stuart J. Russell, Algorithms for inverse reinforcement learning, In Proceedings of the Seventeenth International Conference on Machine Learning (ICML)), pages 663–670. Morgan Kaufmann, 2000.

34.

Matteo Papini, Alberto Maria Metelli, Lorenzo Lupo and Marcello Restelli, Optimistic policy optimization via multiple importance sampling, In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 4989–4999. PMLR, 2019.

35.

T. Parthasarathy, Discounted, positive and noncooperative stochastic games, International Journal of Game Theory 2(1) (1973), 25–37.

36.

Doina Precup, Richard S. Sutton and Satinder P. Singh, Eligibility traces for off-policy policy evaluation, In Pat Langley, editor, Proceedings of the Seventeenth International Conference on Machine Learning (ICML), pages 759–766. Morgan Kaufmann, 2000.

37.

Martin L Puterman, Markov decision processes: discrete stochastic dynamic programming, John Wiley & Sons, 2014.

38.

Giorgia Ramponi, Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni and Marcello Restelli, Truly batch model-free inverse reinforcement learning about multiple intentions, In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108, pages 2359–2369. PMLR, 2020.

39.

Giorgia Ramponi, Alberto Maria Metelli, Alessandro Concetti and Marcello Restelli, Learning in non-cooperative configurable markov decision processes, In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.

40.

Lloyd S. Shapley, Stochastic games, Proceedings of the National Academy of Sciences 39(10) (1953), 1095–1100.

41.

Rui Silva, Gabriele Farina, Francisco S. Melo and Manuela Veloso, A theoretical and algorithmic analysis of configurable mdps, In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS)), pages 455–463. AAAI Press, 2019.

42.

Rui Silva, Francisco S. Melo and Manuela Veloso, What if 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.

43.

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, MIT Press, 2018.

44.

Csaba Szepesvári and Michael L. Littman, Generalized markov decision processes: Dynamic-programming and reinforcement-learning algorithms, In Proceedings of International Conference of Machine Learning (ICML), volume 96, 1996.

45.

Heinrich Von Stackelberg, Marktform und gleichgewicht, J. Springer, 1934.

46.

Yevgeniy Vorobeychik and Satinder P. Singh, Computing Stackelberg equilibria in discounted stochastic games, In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI), 2012.

47.

Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel and Jimmy Ba, Benchmarking model-based reinforcement learning, CoRR, abs/1907.02057, 2019.

48.

Haoqi Zhang, Yiling Chen and David C. Parkes, A general approach to environment design with one agent, In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI)), pages 2002–2014, 2009.

49.

Haoqi Zhang and David C. Parkes, Value-based policy teaching with active indirect elicitation, In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI), pages 208–214. AAAI Press, 2008.

50.

Haoqi Zhang, David C. Parkes and Yiling Chen, Policy teaching through reward function learning. In Proceedings 10th ACM Conference on Electronic Commerce (EC), pages 295–304. ACM, 2009.

51.

Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell and Anind K. Dey, Maximum entropy inverse reinforcement learning, In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI), pages 1433–1438. AAAI Press, 2008.