Parameterized MDPs and Reinforcement Learning Problems - A Maximum Entropy Principle Based Framework

Markov Decision Processes (MDPs) model sequential decision making problems which arise in many application areas such as robotics, sensor networks, economics, and manufacturing. These models are characterized by the state-evolution dynamics $s_{t+1}=f(s_{t},a_{t})$, a control policy $\mu(a_{t}|s_{t})$ that allocates an action $a_{t}$ from a control set to each state $s_{t}$, and a cost $c(s_{t},a_{t},s_{t+1})$ associated with the transition from $s_{t}$ to $s_{t+1}$. The goal in these applications is to determine the optimal control policy that results in a path, a sequence of actions and states, with minimum cumulative cost. There are many variants of this problem [1], where the dynamics can be defined over finite or infinite horizons; where the state-dynamics $f$ can be stochastic; where the models for the state dynamics may be partially or completely unknown, and the cost function is not known a priori, albeit the cost at each step is revealed at the end of each transition. Some of the most common methodologies that address MDPs include dynamic programming, value and policy iterations [2], linear programming [3, 4], and Q-learning [5].

In this article, we view MDPs and their variants as combinatorial optimization problems, and develop a framework based on maximum entropy principle (MEP) [6] to address them. MEP has proved successful in addressing a variety of combinatorial optimization problems such as facility location problems [7], combinatorial drug discovery [8], traveling salesman problem and its variants [7], image processing [9], graph and markov chain aggregation [10], and protein structure alignment [11]. MDPs, too, can be viewed as combinatorial optimization problems - due to the combinatorially large number of paths (sequence of consecutive states and actions) that it may take based on the control policy and its inherent stochasticity. In our MEP framework, we determine a probability distribution defined on the space of paths [12], such that (a) it is the fairest distribution - the one with the maximum Shannon Entropy $H$, and (b) it satisfies the constraint that the expected cumulative cost $J$ attains a prespecified feasible value $J_{0}$. The framework results in an iterative scheme, an annealing scheme, where probability distributions are improved upon by successively lowering the prespecified values $J_{0}$. In fact, the lagrange multiplier $\beta$ corresponding to the cost constraint ($J=J_{0}$) in the unconstrained lagrangian is increased from small values (near 0) to large values to effect annealing. Higher values of multipliers correspond to lower values of the expected cost. We show that as multiplier value increases, the corresponding probability distributions become more localized, finally converging to a deterministic policy.

This framework is applicable to all the classes of MDPs and its variants described above. Our MEP based approach inherits the flexibility of algorithms such as deterministic annealing [7] developed in the context of combinatorial resource allocation, which include adding capacity, communication, and dynamic constraints. The added advantage of our approach is that we can draw close parallels to existing algorithms for MDPs and RL (e.g. Q-Learning) – thus enabling us to exploit their algorithmic insights. Below we highlight main contributions and advantages of our approach.

Exploration and Unbiased Policy: In the context of model-free RL setting, the algorithms interact with the environment via agents and rely upon the instantaneous cost (or reward) generated by the environment to learn the optimal policy. Some of the popular algorithms include Q-learning [5], Double Q-learning [13], Soft Q-learning (entropy regularized Q-learning) [14, 15, 16, 17, 18, 19, 20] in discrete state and action spaces, and Trust Region Policy Optimization (TRPO) [21], and Soft Actor Critic (SAC) [22] in continuous spaces. It is commonly known that for the above algorithms to perform well, all relevant states and actions should be explored. In fact, under the assumption that each state-action pair is visited multiple times during the learning process it is guaranteed that the above discrete space algorithms [5, 13, 14, 15] will converge to the optimal policy. Thus, the adequate exploration of the state and action spaces becomes incumbent to the success of these algorithms in determining the optimal policy. Often the instantaneous cost is noisy [14] which hinders with the learning process and demands for an enhanced quality exploration.

In our MEP based approach, the Shannon Entropy of the probability distribution over the paths in the MDP explicitly characterizes the exploration. The framework results in a distribution over the paths that is as unbiased as possible under the given cost constraint. The corresponding stochastic policy is maximally noncommittal to any particular path in the MDP that achieves the constraint; this results in better (unbiased) exploration. The policy starts from being entirely explorative, when multiplier value is small ($\beta\approx 0$), and becomes increasingly exploitative as the multiplier value increases.

Parameterized MDPs and RL: These class of optimization problems are not even necessarily MDPs which contributes significantly to their inherent complexities. However, we model them in a specific way to retain the Markov property without any loss of generality, thereby making these problems tractable. Scenarios such as self organizing networks [23], 5G small cell network design [24, 25], supply chain networks, and last mile delivery problems [26] pose a parameterized MDP with a two-fold objective of determining simultaneously (a) the optimal control policy for the underlying stochastic process, and (b) the unknown parameters that the state and action variables depend upon such that the cumulative cost is minimized. The latter objective is akin to facility location problem [27, 28, 29], that is shown to be NP-hard [27], and where the associated cost function (non-convex) is riddled with multiple poor local minima.

For instance, Figure 1 illustrates a 5G small cell network, where the objective is to simultaneously determine the locations of the small cells $\{f_{j}\}$ and design the communication paths (control policy) between the user nodes $\{n_{i}\}$ and base station $\delta$ via network of small cells. Here, the state space $\mathcal{S}$ of the underlying MDP is parameterized by the locations $\{y_{j}\}$ of small cells $\{f_{j}\}$.

Algebraic structure and Sensitivity Analysis: In our framework, maximization of Shannon entropy of the distribution over the paths under constraint on the cost function value results in an unconstrained Lagrangian - the free-energy function. This function is a smooth approximation of the cumulative cost function of the MDP, which enables the use of calculus. We exploit this distinctive feature of our framework to determine the unknown state and action parameters in case of parameterized MDPs and perform sensitivity analysis for various problem parameters. Also, the framework easily accommodates stochastic models that describe uncertainties in the instantaneous cost and parameter values.

Algorithmic Guarantees and Innovation: For the classes of MDPs that we consider, our MEP-based framework results into non-trivial derivations of the recursive Bellman equation for the associated Lagrangian. We show that these Bellman operators are contraction maps and use their several properties to guarantee the convergence to the optimal policy and as well as to a local minima in the case of parameterized MDPs.

In the context of model-free RL, we provide comparisons with the benchmark algorithms Q, Double Q, and entropy regularized G-learning [14] (also referred to as Soft Q-learning). Our algorithms converge at a faster rate (as fast as $1.5$ times) than the benchmark algorithms across various values of discount factor, and even in the case of noisy environments. In the context of parameterized MDPs and RL, we address the small-cell network design problem in 5G communication. Here the parameters are the unknown locations of the small-cells and the control policy determines the routing of the communication packet. Upon comparison with the sequential method of first determining the unknown parameters (small cell locations) and then the control policy (equivalently, the communication paths), we show that our algorithms result into costs that are as low as $65\%$ of the former. The efficacy of our algorithms can be assessed from the fact that the solutions in the model-based and model-free cases are nearly the same. We also demonstrate sensitivity analysis, benefits of annealing and considering entropy of distribution over the paths in our simulations on parameterized MDPs and RL.

This paper is organized as follows. We briefly review the related work and MEP [6] in the Section II. In Section III and IV we develop MEP-based framework for MDPs. Section V builds upon the Section III to address the case of parameterized MDPs and RL problems. Simulations on a variety of scenarios are presented in Section VI. We discuss the generality of our framework, its capabilities, and future directions of the work in Section VII. For the ease of reading, we provide a comprehensive list of symbols in the Section F of the supplementary material.

Related Work in Entropy Regularization: Some of the previous works in RL literature [14, 15, 16, 17, 18, 19, 20, 30, 31] either use entropy as a regularization term ($-\log\mu(a_{t}|s_{t})$) [14, 15] to the instantaneous cost function $c(s_{t},a_{t},s_{t+1})$ or maximize the entropy ($-\sum_{a}\mu(a|s)\log\mu(a|s)$) [16, 17, 18] associated only to the stochastic policy under constraints on the cost $J$. This results into benefits such as better exploration, overcoming the effect of noise $w_{t}$ in the instantaneous cost $c_{t}$ and obtaining faster convergence. However, the resulting stochastic policy and soft-max approximation of the value function $J$ is not in compliance with the Maximum Entropy Principle applied to the distribution over the paths of MDP. Thus, the resulting stochastic policy is biased in its exploration over the paths of the MDP. Our simulations demonstrate the benefit of unbiased exploration (in our framework) in terms of faster convergence and better performance in noisy environment in comparison to the entropy regularized benchmark algorithm.

Related Work in Parameterized MDPs and RL: The existing solution approaches [3, 2, 4] can be extended to the parameterized MDPs by discretizing the parameter domain. However, the resulting problem is not necessarily an MDP as every transition from one state to another is dependent on the path (and the parameter values) taken till the current state. Other related approaches for parameterized MDPs are case specific; for instance, [32] presents action-based parameterization of state space with application to service rate control in closed Jackson networks, and [33, 34, 35, 36, 37, 38] incorporate parameterized actions that is applicable in the domain of RoboCup soccer where at each step the agent must select both the discrete action it wishes to execute as well as continuously valued parameters required by that action. On the other hand, the class of parameterized MDPs that we address in this article predominantly originate in network based applications that involves simultaneous routing and resource allocations and pose additional challenges of non-convexity and NP-hardness. We address these MDPs in both the scenarios, where the underlying model is known as well as unknown.

Maximum Entropy Principle: We briefly review the Maximum Entropy Principle (MEP) [6] since our framework relies heavily upon it. MEP states that for a random variable $\mathcal{X}$ with a given prior information, the most unbiased probability distribution given prior data is the one that maximizes the Shannon entropy. More specifically, let the known prior information of the random variable $\mathcal{X}$ be given as constraints on the expectation of the functions $f_{k}:\mathcal{X}\rightarrow\mathbb{R}$, $1\leq k\leq m$. Then, the most unbiased probability distribution $p_{\mathcal{X}}(\cdot)$ solves

where $F_{k}$, $1\leq k\leq m$, are known expected values of the functions $f_{k}$. The above optimization problem results into the Gibbs’ distribution [39] $p_{\mathcal{X}}(x_{i})=\frac{\exp\{-\sum_{k}\lambda_{k}f_{k}(x_{i})\}}{\sum_{j=1}^{n}\exp\{-\sum_{k}\lambda_{k}f_{k}(x_{j})\}}$, where $\lambda_{k}$, $1\leq k\leq m$, are the Lagrange multipliers corresponding to the inequality constraints in (1).

Here we consider the MDPs where the Shannon Entropy $H^{\mu}(s)$ of the distribution $\{p_{\mu}(\omega|s)\}$ over the paths $\omega\in\Omega$ is not necessarily finite (for instance, due to absence of absorption state). To ensure the finiteness of the objective in (III-A) we consider the discounted Shannon Entropy [43, 44]

with a discount factor of $\alpha\in(0,1)$ which we chose to be independent of the discount factor $\gamma$ in the value function $J^{\mu}(s)$. The free-energy function (or, the Lagrangian) resulting from the optimization problem in (III-A) with the alternate objective function $H^{\mu}_{d}(s)$ in (16) is given by

where $\hat{c}_{x_{t}x_{t+1}}^{u_{t}}=c_{x_{t}x_{t+1}}^{u_{t}}+\frac{\gamma^{t}}{\beta\alpha^{t}}\log p_{x_{t}x_{t+1}}^{u_{t}}$, and the subscript $I$ stands for ’infinite entropy’ case. Note that the free-energy functions (7) and (17) differ only with regards to the discount factor $\alpha$ and thus, our solution methodology in this section is similar to the one in Section III-B.

The optimal policy satisfies $\frac{\partial V_{\beta,I}^{\mu}(s)}{\partial\mu(a|s)}=0$, which results into the Gibbs distribution

is the corresponding state-action value function. Substituting the $\mu^{*}_{\beta,I}$ in (19) in the Bellman equation (18) results into the following optimal free-energy function $V_{\beta,I}^{*}(s)(:=V_{\beta,I}^{\mu^{*}_{\beta,I}}(s))$.