An Information-theoretic On-line Learning Principle for Specialization in Hierarchical Decision-Making Systems
Heinke Hihn Sebastian Gottwald Daniel A. Braun
cs.LG cs.IT math.IT stat.ML

Supplementary
    Isabel Funke1 Sebastian Bodenstedt1 Florian Oehme2 Felix von Bechtolsheim2 Jürgen Weitz2,3 Stefanie Speidel1,3
    December 30, 2023
==================================================================================================================

empty
empty


Information-theoretic bounded rationality describes utility-optimizing decision-makers whose limited information-processing capabilities are formalized by information constraints. One of the consequences of bounded rationality is that resource-limited decision-makers can join together to solve decision-making problems that are beyond the capabilities of each individual. Here, we study an information-theoretic principle that drives division of labor and specialization when decision-makers with information constraints are joined together. We devise an on-line learning rule of this principle that learns a partitioning of the problem space such that it can be solved by specialized linear policies. We demonstrate the approach for decision-making problems whose complexity exceeds the capabilities of individual decision-makers, but can be solved by combining the decision-makers optimally. The strength of the model is that it is abstract and principled, yet has direct applications in classification, regression, reinforcement learning and adaptive control.




§ INTRODUCTION

Intelligent learning systems are often formalized as decision-makers that learn probabilistic models of their environment and optimize utilities. Such utility functions can represent different classes of problems, such as classification, regression or reinforcement learning. To enable these agents to learn optimal policies, it is usually too costly to enumerate all possibilities and determine the expected utilities. Intelligent agents must instead invest their limited resources such that they optimally trade off utility versus processing costs <cit.>, which can be formalized in the framework of bounded rationality <cit.>. The information-theoretic approach to bounded rationality <cit.> provides an abstract model to formalize how such agents behave in order to maximize utility within a given resource limit, where resources are quantified by information processing constraints <cit.>.

Intriguingly, the information-theoretic model of bounded rationality can also explain the emergence of hierarchies and abstractions, in particular when multiple bounded rational agents are involved in a decision-making process <cit.>. In this case an optimal arrangement of decision-makers leads to specialization of agents and an optimal division of labor, which can be exploited to reduce computational effort <cit.>. 

Here, we introduce a novel gradient-based on-line learning paradigm for  hierarchical decision-making systems. Our method finds an optimal soft partitioning of the problem space by imposing information-theoretic constraints on both the coupling between expert selection and on the expert specialization. We argue that these constraints enforce an efficient division of labor in systems that are bounded. As an example, we apply our algorithm to systems that are limited in their representational power—in particular by assuming linear decision-makers that can be combined to solve problems that are too complex for each decision-maker alone.

The outline of this paper is as follows: first we give an introduction to bounded rationality, next we introduce our novel approach and demonstrate how it can be applied to classification, regression, non-linear control, and reinforcement learning. At last, we conclude.



§ BACKGROUND



 §.§ Bounded Rational Decision Making


An important concept in decision-making is the Maximum  Utility principle <cit.>, where an agent always chooses an optimal action a_s^* ∈𝒜 such that it maximizes their expected utility depending on the context s ∈𝒮, i.e.

    a^*_s = _a 𝐔(s, a),

where the utility is given by a function 𝐔(s, a) and the states are distributed according to a known and fixed distribution p(s). Solving this optimization problem naively leads to exhaustive search over all possible (a,s) pairs, which is in general a prohibitive strategy. One possible approach to this is studying decision-makers that have limited processing power, e.g. that have to act within a given time limit. Instead of finding an optimal strategy, a bounded rational decision-maker optimally trades off expected utility and the processing costs required to adapt the system. In this study we consider the information-theoretic free energy principle <cit.> of bounded rationality, where the decision-maker's behavior is described by a probability distribution p(a|s) over actions a given a particular state s and the decision-maker‘s processing costs are given by the Kullback-Leibler divergence (p(a|s)||p(a)) = ∑_ap(a|s) logp(a|s)/p(a)
between the agent‘s prior distribution over the actions p(a) and the posterior policies p(a|s).

We can model the decision-maker's processing power by defining an upper bound B on the average  the agent can maximally spend to adapt its prior behavior, which results in the following constrained optimization problem:

    max_p(a|s)∑_s,a p(s)p(a|s)𝐔(s, a)
     s.t. 𝔼_p(s)[(p(a|s)||p(a))] ≤B.

This constraint can be regarded as a regularization imposed on the forms the distributions can take. The resulting constrained optimization problem can be transformed into an unconstrained variational problem by introducing a Lagrange multiplier  β∈ℝ^+ that governs the trade-off between expected utility gain and information cost <cit.>:

    max_p(a|s)𝔼_p(s|a)[𝐔(s, a)] - 1/β𝔼_p(s)[(p(a|s)||p(a))].

For β→∞ the agent acts perfectly rational and for β→ 0 the agent can only act according to the prior. The optimal prior in this case is given by the marginal p(a) = ∑_s ∈ Sp(s) p(a|s). The solution to this optimization problem can be found by applying Blahut-Arimoto type algorithms, similar to Rate-Distortion Theory <cit.>.



  §.§.§ Hierarchical Decision Making
 Combining several bounded-rational agents by a selection policy allows for solving optimization problems that exceed the capabilities of the individual decision-makers <cit.>. To achieve this, the search space is split into optimal partitions, that can be solved by the individual decision-makers. A two stage mechanism is introduced: The first stage is comprised of an expert selection policy p(x|s) that chooses an expert x based on the past performance of x given the state s. This requires a high processing power in the expert selection, such that an optimal mapping from states to experts can be learned. The second stage chooses an action according to the expert's policy p(a|s,x). The optimization problem given by (<ref>) can be extended to incorporate a trade-off between computational costs and utility in both stages in the following way:

    max_p(a|s,x), p(x|s)[𝐔(s,a)] - 1/β_1I(S;X) - 1/β_2I(S;A|X),

where β_1 is the resource parameter for the expert selection stage and β_2 for the experts. I(·;·) is the mutual information between the two random variables. The solution can be found by iterating the following set of equations <cit.>: 

    [                          p(x|s)                               =       1/Z(s)p(x) exp(β_1 (s,x));                            p(x)                               =                 ∑_s p(s) p(x|s);                        p(a|s,x)                               = 1/Z(s,x) p(a|x) exp(β_2 𝐔(s,a));                          p(a|x)                               =            ∑_s p(s|x)p(a|s,x) ,;                                 ]

where Z(s) and Z(s,x) are normalization factors and (s,x) = _p(a|s,x)[𝐔(s,a)] - 1/β_2(p(a|s,x)|| p(a|x)) is the free energy of the action selection stage. The effective distribution p(a|s) encapsulates a mixture-of-experts policy consisting  of the experts p(a|s,x) weighted by the responsibilities p(x|s). Note that the Bayesian posterior is not determined by a given likelihood model, but is the result of the optimization process (<ref>). The hierarchical system is depicted in Figure <ref>.



 §.§ Maximum Entropy Reinforcement Learning

We model sequential decision problems by defining a Markov Decision Process as a tuple (𝒮, 𝒜, P, r), where 𝒮 is the set of states, 𝒜 the set of actions, P: 𝒮×𝒜×𝒮→ [0,1] is the transition probability, and r: 𝒮×𝒜→ℝ is a reward function. The aim is to find the parameter θ of a policy π_θ that maximizes the expected reward:


    θ^* = _θ𝔼_τπ_θ[∑_t=0^∞ r(s_t, a_t)]_J(π_θ).

We define r(τ) = ∑_t=0^∞ r(s_t, a_t) as the cumulative reward of trajectory τ = {(s_t, a_t)}_t=0^∞,  which is sampled by acting according to the policy π, i.e. (s, a)∼π(·|s), and s_t+1∼ P(·|s_t, a_t).
Learning in this environment can then be modeled by reinforcement learning <cit.>, where an agent interacts with an environment defined by the tuple (𝒮, 𝒜, P, r) over a number of (discrete) time steps t. At each time step t, the agent receives a state s_t and selects an action a_t according to the policy π(a_t|s_t). In return, the agent receives the next state s_t+1 and a scalar reward r_t. This process continues until the agent reaches a terminal state after which the process restarts. The goal of the agent is to maximize the expected return from each state s_t, which is typically defined as the infinite horizon discounted sum of the rewards. A common choice to achieving this is Q-Learning <cit.>, where we make use of an action-value function that is defined as the discounted sum of rewards:

    Q(τ) =∑_t=0^∞γ^t r(s_t, a_t),

and γ∈ (0, 1] is a discount factor.
Learning the optimal policy can be achieved in many ways. Here, we consider Policy gradient methods <cit.> which are a popular choice to tackle reinforcement learning problems. The main idea is to directly manipulate the parameters θ of the policy in order to maximize the objective J(π_θ) by taking steps in the direction of the gradient ∇_θ J(π_θ). The gradient of the policy can be written as 

    ∇_θ J(π_θ) = 𝔼_τ∼π_θ[∇_θlogπ_θ(τ)Q(τ)],

where π_θ(τ) = p(s_0) Π_t=0^Tπ_θ(a_t|s_t)p(s_t+1|s_t,a_t) is the probability of a trajectory τ. This result of the policy gradient theorem has inspired several algorithms, which often differ in how they estimate the cumulative reward, e.g. Q-Learning <cit.>,  the REINFORCE algorithm <cit.>, and Actor-Critic algorithms <cit.>. In this study we will introduce an hierarchical Actor-Critic algorithm.

To balance exploration vs. exploitation <cit.> maximum entropy reinforcement learning introduces an additional policy entropy term as a penalty to the value function. The optimal value function under this constraint is defined as 

    π^*(a|s) = max_π𝔼_π[∑_t=0^∞γ^t ( r(s_t, a_t) - 1/βlogπ(a|s))].

Here, β trades off between reward and entropy, such thath β→∞ recovers the standard RL value function and β→ 0 recovers the value function under a random policy.
One can define this objective as an inference problem <cit.> by specifying a fixed prior distribution π_0(a) over trajectories. In the next sections we generalize this assumption by assuming the prior distribution to be part of the optimization problem, as discussed in the earlier section on bounded rationality. 







§ SPECIALIZATION IN HIERARCHICAL SYSTEMS


In this section we introduce our novel gradient based algorithm to learn the components of a hierarchical multi-agent policy. Information-theoretic bounded rationality argues that hierarchies and abstractions emerge when agents have only limited computational resources <cit.>. In particular, we leverage the hierarchical model introduced earlier to learn a disentangled representation of the state and action spaces. We will see how limiting the amount of uncertainty each agent can reduce leads to specialization. First we will show how this principle can be transformed into a general on-line learning algorithm and afterwards we will show how it can be applied to classification as an illustrative example and reinforcement learning. In the following we will derive our algorithm with a focus on reinforcement learning.

The model consists of two stages: an expert selection stage, and an action selection stage. The first stage learns a soft partitioning π(x|s) of the state space and assigns each partition optimally to the experts according to a parametrized policy π_θ(x|s) with parameters θ such that ∑_x π_θ(x|s) (s,x) is maximized under an information-theoretic constraint on 𝔼[(π_θ(x|s)||π(x))]. The second stage is defined by a set of policies π_ϑ(a|s,x) that maximize the expected utility ∑ p(s|x)∑ p_θ(a|s,x)𝐔(s,a) for each expert x. We device a gradient based on-line learning algorithm to find the optimal parameters in the following. 

Firstly, we note that in the reinforcement learning setup the utility 𝐔(s,a) is given by the reward function r(s,a). And secondly that in maximum entropy RL the regularization penalizes deviation from a fixed equally distributed prior, but in a more general setting we can discourage deviation from an arbitrary prior policy by optimizing for: 


    _π𝔼_π[∑_t=0^∞γ^t ( r(s_t, a_t) -  1/βlogπ(a_t|s_t)/π(a))].

As discussed in Section <ref> the optimal prior (in terms of an optimal utility vs. processing cost) is the marginal of the posterior policy given by π(a) = ∑_s p(s) π(a|s). We can incorporate this into the optimization problem (<ref>) by rewriting it to:

    max_π_ϑ(a|s,x), π_θ(x|s)∑_s,x,ap(s)  π_θ(x| s) π_ϑ(a| s,x)J(s,x,a)

where the objective J(s,x,a) is given by


    J(s,x,a) = 𝐔(s,a) - 1/β_1logπ_θ(x| s)/π(x) - 1/β_2logπ_ϑ(a| s,x)/π(a | x),

and θ, ϑ are the parameters of the selection policy and the expert policies, respectively. Note that each expert policy has a distinct set of parameters ϑ_x, i.e. ϑ = {ϑ_x}_x, but we drop the x index for readability. Considering our algorithm is on-line and the action space is continuous, it would be prohibitive to compute the prior in each step. Instead we approximate the prior distributions π(x) and π(a|x) by exponential running mean averages of the posterior policies with momentum terms λ_1 and λ_2:

    π_t+1(a|x)    =   λ_1π_t(a|x) + (1 - λ_1)π_ϑ(a|s,x) 
    π_t+1(x)    =   λ_2π_t(x) + (1 - λ_2)π_θ(x|s)

In our experiments we set λ_1, λ_2 to 0.99.
To optimize the objective we define two separate value functions: one to estimate the discounted sum of rewards and one to estimate the free energy of the expert policies. The discounted reward for the experts is 

    R_t = ∑_l=0^Tγ^lr(s_t+l, a_t+l),

which again we learn by parameterizing the value function with a neural network and performing regression on

    ϕ^* = _ϕ1/|𝒟|T∑_τ∈𝒟∑_t=0^T (V_ϕ(s_t) - R_t)^2,

where ϕ are the parameters of the value net and 𝒟 is a set of trajectories τ up to horizon T collected by roll-outs of the policies. Similar to the discounted reward R_t we can now define the discounted free energy F_t as

    F_t = ∑_l=0^Tγ^l f(s_t+l, x_t+l, a_t+l),

where f(s,x,a) = r(s, a) - 1/β_2logπ_ϑ(a|s,x)/π(a|x). The value function F_t is learned by parameterizing the value function with a neural network and performing regression on the mean-squared-error:

    φ^* = _φ1/|𝒟|T∑_τ∈𝒟∑_t=0^T (V_φ(s_t) - F_t)^2,

where φ are the parameters of the value net, and 𝒟 is a set of trajectories.



 §.§ Expert Selection
 
The selector network learns a policy π_θ(x| s) that maps states s to expert policies x, based on their performance in the past. The resource parameter β_1 constrains how well this gating step can differentiate between the experts. For β_1 → 0 the selection maps each state s equally distributed to each experts or all to one single expert, depending on β_2. For β_1 →∞, π_θ(x| s) converges to the perfectly rational selector which always chooses the optimal expert x. Thus, the expert selection stage optimizes the following objective:

    max_θ_π_θ(x|s)[f̂(s,x) - 1/β_1logπ_θ(x|s)/π(x)],

where f̂(s,x) = 𝔼_π_ϑ(a|s,x)[f(s, x, a)], which is the free energy of the expert. The gradient of J(θ) is then given (up to an additive constant) by 

    [∇_θlogπ_θ(x | s)(f̂(s, x) - 1/β_1logπ_θ(x|s)/π(x)) ].

The double expectation can be replaced by Monte Carlo estimates, where in practice we use a single (s,x,a) tuple for f̂(s,x).
This formulation is known as the policy gradient method <cit.> and is prone to producing high variance gradients. A common technique to reduce the variance is to formulate the updates using the advantage function instead of the reward <cit.>. The advantage function A(a_t,s_t) is a measure of how well a certain action a performs in a state s compared to the average performance in that state, i.e. A(a,s) = Q(s,a) - V(s). Here, V(s) is called the value function and is a measure of how well the agent performs in state s, and Q(s,a) is an estimate of the cumulative reward achieved in state s when the agent executes action a. Thus the advantage is an estimate of how advantageous it is to pick a in state s in relation to a baseline performance V(s). Instead of learning the value and the Q function, we can approximate the advantage function in the following way:

    Â^F_t = f(s_t, x_t, a_t) + γ V_ϕ(s_t+1)_≈ Q(s_t, a_t) - V_ϕ(s_t).

This yields the following gradient estimates for the selector:

    ĝ_s = 1/|𝒟|∑_τ∈𝒟∑_t=0^T∇_θlogπ_θ(x_t|s_t)Â^F_t,

where 𝒟 is a set of trajectories τ produced by the policies. This formulation allows us to perform the updates as in Advantage-Actor-Critic-Models. The expectation can be estimated via Monte Carlo sampling which enables us to employ our algorithm in an on-line optimization fashion.



 §.§ Action Selection
 
The actions a are given by the posterior action distribution of the experts. Each expert x maintains a policy for each of the world states s and updates those according to the utility/cost trade-off. The advantage function for each expert is given as

    Â_t = r(s_t, a_t) + γ V_φ(s_t+1) - V_φ(s_t).

The objective of this stage is then to maximize the expected advantage _p(a|s,x)[Â_t], yielding the gradient estimates

    ĝ_x = 1/|𝒟|∑_τ∈𝒟∑_t=0^T∇_ϑlogπ_ϑ(a_t|x_t,s_t)Â_t

for each of the experts.

The algorithm we propose to find such an optimal hierarchical structure is based on the alternating optimization paradigm <cit.>. During one phase the expert selector distribution π(x|s) is optimized while the action selectors are held fixed and vice versa. The length of the phases can either be fixed or limited by checking for a convergence criterion. The complete algorithm is given in Algorithm <ref>.




§ EXPERIMENTS AND RESULTS

In the following we will show how our approach can be applied to learning tasks where the overall complexity of the problem exceeds the processing power of (linear) experts. In particular, we will look at classification, regression, non-linear control (gain scheduling), and reinforcement learning. In our experiments we model the selector and both value functions as artificial neural networks and train them according to the gradient estimates we derived in Section <ref>.



 §.§ Classification and Regression with Linear Decision-Makers


When dealing with complex data for classification (or regression) it is often beneficial to combine multiple classifiers (or regressors). In the framework of ensemble learning, for example, multiple classifiers are joined together to stabilize learning and improve the results <cit.>, such as Mixture-of-Experts <cit.> and Multiple Classifier systems <cit.>. The method we propose when applied to classification problems can be interpreted as a member of this family of algorithms. The application to regression could be considered as an example of local linear regression <cit.>. In accordance with Section <ref> we define the utility as the negative loss, i.e. U(ŷ, y) = -ℒ(ŷ,y), where ŷ is the action of the expert, i.e. the estimated class label or the estimated regression value, and y is the ground truth, and s are the input features. For classification, we chose the cross-entropy loss ℒ(y, ŷ) = ∑_i y_i log1/ŷ_i = -∑_i y_i logŷ_i as a  performance measure, for regression the mean squared error ℒ(y, ŷ) = ∑_i (ŷ_i-y_i)^2. The objective for expert selection becomes 

    max_θ_p_θ(x|s)[f̂(x,s) - 1/β_1logp_θ(x|s)/p(x)],

where f̂(x,s) 𝔼_p_ϑ(ŷ|x,s)[-ℒ(ŷ,y) - 1/β_2logp_ϑ(ŷ|s,x)/p(ŷ|x)], i.e. the free energy of the expert x. For action  selection the objective then becomes

    max_ϑ_p_ϑ(ŷ|x,s)[-ℒ(ŷ,y) - 1/β_2logp_ϑ(ŷ|s,x)/p_(ŷ|x)].

To find an optimal partitioning we consider the limit β_1→∞. We evaluated our method on three synthetic datasets for classification—see Figure <ref>—, and one synthetic dataset for regression—see Figure <ref>. Our method is able to partition the problem set into subspaces and fit a linear decision-maker on each subset. This is achieved by the emergence of a hierarchy of specialized agents, as is evidenced by the emerged state partitioning. We implemented our experiments using TensorFlow <cit.> and scikit-learn <cit.>.







 §.§ Gain Scheduling by Combining Linear Decision-Makers


When dealing with non-linear dynamics one approach is to decompose it into several linear sub-problems and design linear controllers for each sub-problem. This method is known as gain scheduling and is a well established method in the control literature <cit.>. In some cases it is possible to find auxiliary variables that correlate well with the changes in the underlying dynamics. It is then possible to reduce the effects of the parameter variations simply by changing the parameters of the regulator as a function of the auxiliary variables. For example, in flight control systems the Mach number and the dynamic pressure are measured by sensors and used as scheduling variables. A main problem in designing such systems is to find suitable scheduling variables. This is usually done by incorporating prior knowledge about the system dynamics. Here, we demonstrate how our approach can be applied to automatically learn the scheduling regions and pertinent linear controllers without pre-specifying the operating points. As an illustrative example, consider a scalar non-linear plant defined by the following piecewise linear dynamics:

    ẋ = A_ix + B_iu + ϵ,     for  x ∈ X_i

where x is the system state, A_i are the system matrices, B_i are the control matrices and ϵ is a random Gaussian noise source. Here, {X_i} is a state partition into piecewise linear (affine) control regimes.  To approach this problem, we denote the plant state as states s, the control signal u as the action and learn a set of linear Gaussian control policies (i.e. the experts), where we perform gradient descent to find the optimal parameters, as described in Section <ref>. 

Consider the following operation regimes:

    B_i =
    
    1    if  x ∈ X_0  
    
    -1     if  x ∈ X_1,

where X_0 = {x|x ≥ 0} and X_i = {x|x < 0}. Assuming quadratic costs J = 1/2∑_t=0^T Qx_t^2 + Ru_t^2, it is straightforward to find an optimal controller for each partition X_i and we can switch between the regimes by defining the system state as the scheduling variable. We set Q = 1.0 and R = 0.01 and T=64 and find the optimal gains K_0 = 11.05 and K_1 = -11.05, for regimes X_0 and X_1 respectively.
Obviously, this is only possible if the plant dynamics are known. In contrast, our algorithm is able to learn the scheduling policy and the control policy automatically, which is shown in Figure <ref>. The gains found by our algorithm were K_0 = 9.99 and K_1 = -9.71 and achieve a control cost of J = -934 compared to J = -1004 achieved by gain scheduling. We set the noise source to ϵ𝒩(0, 0.25), causing the control policy to shift when the plant state is close to zero. The prior is p(x) = (0.55, 0.45), showing that both expert policies were used to control the plant. The mutual information of I(S;X) ≈ 0.85 bits and the entropy of p(x|s) decaying towards 0 show that the selector successfully learns to partition the state space. The resource parameter was set to β_2 = 0.001 to drive specialization.






 §.§ Reinforcement Learning with Linear Decision-Makers


In the following we will show how our hierarchical system is able to solve a continuous reinforcement learning problem using an optimal arrangement of linear control policies. We evaluate on a task known as Acrobot <cit.>, more commonly referred to as the inverted double pendulum. The task is to swing  a double-linked pendulum up and keep it balanced as long as possible. The agent receives a reward of 10 plus a distance penalty between its actual state and the goal state. The episode is terminated if the agent reaches a predefined terminal state (hanging downwards) or after 1000 time steps. To balance the pendulum the agent is able to apply a force to the central joint of a ∈ [-1, +1], i.e. move it to the left or the right, respectively. This environment poses a non-linear control problem and can thus not be solved optimally by a single linear controller. We show that using our approach, a committee of linear experts can solve this non-linear task. The results are shown in Figure <ref>. We allowed for five experts (both with β_2 = 0.001), but our system learns that three experts are sufficient to solve the task. The priors for each expert (lower right Figure, each color represents an expert) center on -1, 0, and 1, which correspond to swinging the double pendulum to the left, no force, and swinging to the right, respectively. The remaining two experts overlap accordingly. We can see that the average (π_ϑ(a|x,s)||π(a|x)) in the five expert setup decreases, while the selection (π_θ(x|s)||π(x)) increases to ≈ 1.5. Both indicate that the system has learned an optimal arrangement of three experts and is thus able to achieve maximum reward and eventually catches up to the performance of TRPO, which is our nonlinear control baseline that was trained with three-layered policy and value neural networks consisting of ReLu activation functions. Our method successfully learned a partitioning of the double-pendulum state space without having any prior information about any of the system dynamics or the state space. We implemented our experiments in TensorFlow <cit.> and OpenAI Gym <cit.>.





§ DISCUSSION


Recently, there has been increased interest in investigating the effects of information-theoretic constraints on reinforcement learning tasks with mixture-of-experts policies. For example, the authors of <cit.> have proposed a divide-and-conquer principle for policy learning in a reinforcement learning setting. They argue that splitting a central policy into several sub-policies improves the learning phase by requiring less samples overall. To implement this idea they split the action and state space into pre-defined partitions and train policies on these partitions. The information-theoretic constraints during training enforce that multiple experts are kept similar to each other,  so that the expert policies can be fused into one central policy. In contrast, in our approach the information-theoretic constraints enforce that all experts stay close to their respective priors thereby generating as little informational surprise as possible. This leads to specialization of experts, because each expert is assigned a sub-space of the input space where information can be processed efficiently without deviating too much from the optimal prior adapted to that region. Crucially, in our setup the partitioning is not predefined but part of the optimization process.

Our approach belongs to a wider class of models that use information constraints for regularization to deal more efficiently with learning and decision-making problems <cit.>. One such prominent approach is Trust Region Policy Optimization (TRPO) <cit.>. The main idea is to constrain each update step to a trust region around the current state of the system. This region is defined by the Kullback-Leibler Divergence (π_new||π_old) between the old policy and the new policy. The smooth updates provide a theoretic monotonic policy improvement guarantee. Another similar approach are relative entropy policy search methods <cit.>, where the idea is to learn a gating policy that can decide which sub-policy to choose. To achieve this the authors impose a  constraint between the data distribution and the next policy. 

Another related approach to ours are Mixture of Experts (ME) models, originally introduced by <cit.> as a tree structure to solve complex classification and regression tasks by leveraging the divide and conquer paradigm. MEs consist of three main components: gates, experts, and a probabilistic model that combines the expert predictions. The objective of the gate is to find a soft partitioning of the input space and assign partitions to experts which perform best on the partition. Experts are built to perform optimally in regression or classification tasks given an assigned partition. The model is a weighted sum of the experts outputs, weighted by how confident the gate is in the experts opinion. MEs exhibit a high degree of flexibility as evidenced by the variety of models and algorithms employed in the three components <cit.>. Our model allows learning such models, but can also be applied to more general decision-making scenarios like reinforcement learning.

Prior work to ours in the control literature working on a similar setup  assumed the system dynamics to be given. e.g. in <cit.>. The authors of <cit.> split the state space of the inverted pendulum into predefined bins and find a linear controller that stabilizes each bin by learning a selection policy over these predefined controllers. Our approach differs from these by the fact that we take only the reward signal and perform a partitioning of the state space and learning linear controller on these partitions simultaneously. This poses a difficult learning problem as both system parts have to adjust to one another on different timescales. Other decentralized approaches (e.g. <cit.>) have trained separate decentralized models to fuse them into a single model that can be used by a reinforcement learning agent. In contrast, our method learns several sub-policies.

In summary, we introduce a promising novel gradient based on-line learning paradigm for hierarchical multi-agent systems. Our method finds an optimal soft partitioning by considering the agents' limitations in terms of information-theoretic constraints, supporting expert specialization. Importantly, our model is capable of doing so without any prior information about the task. This becomes especially difficult in continuous control tasks, where the system dynamics are unknown. Our method is abstract and principled in a way that allows it to be employed on a variety of tasks including multi-agent decision-making, mixture-of-expert regression, and divide-and-conquer reinforcement learning.
An open questions remains how to apply our method to high dimensional control tasks.


plain






























