This article shows how to learn both the structure and the parameters of partially observable environment simultaneously while also online performing near-optimal sequence of actions taking into account exploration-exploitation tradeoff. It combines two results of recent research: The former extends model-based Bayesian reinforcement learning of fully observable environment to bigger domains by learning the structure. The latter shows how a known structure can be exploited to model-based Bayesian reinforcement learning of partially observable domains. This article shows that merging both approaches is possible without too excessive increase in computational complexity.
Partially observable Markov decision processes
(POMDPs) are a well known framework for
modeling and planning in partially observable stochastic
environments [
Such plans could be used in robotics, in dialogue
management or elsewhere. However, the range of their
practical applicability is limited by several difficulties. Firstly,
their usage is limited to small state spaces only (curse
of dimensionality) even when using several
approximations [
Secondly, it could be difficult for an expert to specify the
probabilities exactly when applying POMDP to some
domain. There were several attempts to overcome this
problem by learning the model [
Following the recent research this article proposes an approach which could solve both problems at the same time.
Learning the model by interacting with the environment
(reinforcement learning) was researched a lot [
If the structure were not known then learning it would
be a challenging problem even in fully observable
environments. Ross and Pineau [
This article addresses generalization of the tasks
mentioned above. We show the way to navigate an agent in an
unknown stochastic dynamic partially observable
environment using near optimal actions. To do so, we combine the
algorithm [
We take the best ideas of each of them. Right after
explaining the basic preliminaries in section 2 and
demonstrating them on an example in section 3 we present an
analytical representation of the belief over parameters
(analogous to [
POMDPs usually model unknown environments as follows. At each time step the environment with the agent is in an unobserved state s ∈ S. At this time step agent receives observation o ∈ O and reward r. Then the agent is free to choose an action a ∈ A. As the time advances, the state changes to a new state s′ that stochastically depends on previous state and action.
We are interested in the special case of POMDPs where the state space factorizes along several state variables X ∈ X hence each state s is a vector s = (s1, ...s| X| ) ∈ S = ∏X∈X.
Rewards and observations behave analogously r ∈ ∏R∈R and o ∈ ∏O∈O.
Moreover we can assume without loss of generality that O ⊆ X and R ⊆ X. It implies that the observation is the state restricted to observation variables. It will be denoted as o = sO. Other restriction operations will be denoted analogously. For an instance, values of reward variables in the state s can be denoted sR.
We will always restrict vectors which are denoted by bold lower case letters to sets of variables denoted as bold upper case letters. Capital letter which wont’ be bold will denote single variable. Lower case non-bold letter will be its value. Specially in the case when G is
the graph of a Bayesian network, PAGX we will denote set of variables which are parents3 of variable X in graph G. Values of variables of parents of X will be denoted paGX where X ∈ X.
When the time advances to the next step the state s changes to s′ according to unknown transition probability P(s′| s, a).
We assume that the transition probability P(s′| s, a) factorizes according to a dynamic Bayesian network with unknown structure G with unknown parameters.
Dynamic Bayesian network with structure G is described as Bayesian network which has X′ ∪ X ∪ { A} as its nodes. By (s′, s, a)PAGX we denote (s′, s, a) restricted to the variables which are parents of variable X according to structure G.
To emphasize that we take P(s′X | (s′, s, a)PAGX ) as an unknown parameter, we will denote it: (1) (2) θX(s′,s,a)PAGX .
It is actually a vector of real values between 0 and 1 summing to 1 containing for each value s′X the probability P(s′X | (s′, s, a)PAGX ). As the indexes suggest that we have such a set of parameters for each state variable X and for each combination of values of its parents.
Even though we do not assume structure G to be known we still assume that a prior probability distribution P(G) over structures G is known. This probability distribution can express experts’ prior knowledge or it can just prefer simple structures over more complicated ones.
The transition probability can be expressed as: P(s′| s, a) = ∑ P(G) · P(s′| s, a, G).
G
We assume that the parameters θX(s′,s,a)PAGX follow the Dirichlet distribution, which is conjugate to multinomial distribution.
The hyperparameters are initially set to one or set to the
values that preserve the likelihood of equivalent
parameters in equivalent Bayesian networks (see [
Each unknown parameter θX(s′,s,a)PAGX can be regarded as an additional state feature.
This way a POMDP with unknown parameters can be converted into a bigger POMDP without unknown parameters. Similar remark also holds for the unknown structure. It can be also regarded as a part of the state hence POMDP 3Parent variable V of variable W is a term used in Bayesiannetworksl-iterature to denote that there is an arrow from V to W in the graph of Bayesian network. This is in greater detail explained in section 3. with unknown structure and parameters can be regarded as a bigger POMDP with known dynamics.
POMDP agent is usually maintaining so called belief state b(s˜) which represents probability distribution over possible states. In our case s˜ consists not only of the current state s but also of the graph structure and its parameters.
Surprisingly, as Poupart and Vlassis showed [
There is only a finite number of possible graphical structures implying that the whole belief b(s˜) can be maintained in a closed form. But the number of possible graphs may be large. That is why approximation is introduced in section 5.
The belief is a sufficient statistic for taking a decision. Agents’ overall algorithm is summarized in algorithm 1.
Data: b initial belief over current state, structures and their parameters 1 while not TerminationCondition() do 2 a := selectAction(b).action; 3 performAction(a); 4 o := receiveObservation(); 5 b := updateBelief(b,a,o); 3
For better readability we illustrate the terms on a problem
taken from [
This corresponds to algorithm 1. Choosing and performing action is on its lines 2 and 3. After the agent listens or opens a door it knows what it has heard or whether it met a tiger or found a fortune. This is shown on line 4 of algorithm 1. Agent then uses this observation to update its belief on line 5. The belief contains all information the agent knows i.e. the agent should count how many times it has heard the the tiger on each side and estimate where the tiger is. It should also learn usual tiger position and other facts about the environments’ behaviour. These information are also stored and updated with belief. We assume that after opening a door and finding a tiger or a fortune the experiment restarts itself and the tiger is again
At placed behind random door. Everything repeats until a termination condition is reached (line 1). This unspecified condition allows for example infinite repetition of the experiment until the user terminates it.
This scenario can be modelled as follows. The set of actions A contains actions for going left, right and listening.
A ∈ { le f t, right, listen}
The set of reward variables R contains only one variable, namely the variable Reward.
R = { Reward}
We assume that domains of all variables are known. Hence the domain of variable Reward is also assumed to be known. Let us say that cost of listening is 1, cost of facing a tiger 100 and reward for finding a fortune 10. Then Reward ∈ {− 1, −100, 10} .
The set of state variables X contains variables Tiger, Heard and Reward.
X = { Tiger, Heard, Reward}
Tiger is position of the tiger and Heard is a variable containing what has the agent heard.
From this three variables the variable Tiger is unobserved because agent doenst’ know the position of the tiger. Other two variables are observed.
O = { Heard, Reward}
The agent knows neither the state transition probabilities nor the structure between the variables. It has to learn it first. The real graphical structure could be for example like figure 1.
The node shapes have its usual meaning. Squares denote the decision(action) variables. Circles denote random variables and diamonds denote reward variable.
As we are modelling a dynamic environment. We have a copy of each variable for each time step. The figure shows only two time slices - for time t and t + 1. We have also shown only the arrows which point to time t+1. We have omitted all other arrows.
An arrow starts in a node called parent and goes to a node called child. As each node is a variable we interchange the term parent node and parent variable.
The intuitive meaning of arrows is this: The child node(variable) X stochastically depends only on combination of values of parent variables. More rigorous meaning of an arrow is that child variable X is conditionally independent on all other variables given values paGX of its parents PAGX .
Let G denote the graph from figure 1. Then PAGRewardt+1 = { At , Tigert } which is quite natural. The reward which agent will receive depends on the combination where it decided to go and where the tiger has been. This dependence in our example is even deterministic. However this is not general.
For example the variable Heardt+1 depends on its parents stochastically. The reason for it is simple. The agent could independently of the current state randomly hear incorrectly. PAGHeardt+1 = { At , Tigert } because what the agent hears depends on where the tiger is and on the fact whether the agent even listed.
In order to make it possible for the agent to learn the environment it is necessary to let the agent interact with the environment repeatedly. So the experiment with tiger restarts itself everytime the agent opens a door. The tiger is then again placed behind a random door. That is why PAGTigert+1 = { At , Tigert } .
Each variable in this example has two parents: the ternary action variable and one binary variable. Hence to specify the probability distribution over child variable we need to specify the probability of each of its values for all six combinations of values of parent variables ie. we need to specify P(s′X | (s′, s, a)PAGX ). It is specified by 2 ∗ 3 = 6 probability distributions over values of child variable. As all child variables are binary we need to specify 6 pairs of numbers between 0 and 1 such that each pair sums to 1.
These pairs of numbers are denoted as in (1).
We interchangeably call such pairs or even above mentioned 6-tuples of pairs parameters in plural or a parameter in singular. By substituting values to s, s′ and a one can restrict the parameter to one concrete value.
For example let us assume that the agent is listening. The tiger is behind the right door and that the probability of correct listening is 0.9 and the probability of opposite listening outcome is 0.1 then following equalities would hold:
P(s′Heard | (s′, s, a)PAGHeard ) = θ H(reiagrhdt,listen) = (0.9, 0.1).
At Tigert
paGHeard = (s′, s, a)PAGHeard = (right, listen).
The agent doesnt’ know the value of mentioned parameter and as was already explained in previous section the agent can treat parameters as random variables. This converts the POMDP with unknown parameters to a bigger POMDP with known parameters. The structure of this POMDP is shown in figure 2.
Notice that we dont’ have a copy of these parameterrandom-variables for each time slice. All time slices share the same parameter. That is because the parameter doesnt’ change over time.
Information about possible values of these parameters, along with possible structures and states are maintained in the belief, which is described in following sections. 4
We begin by describing how belief looks like when we are
given the structure. It is exactly the same as described by
Poupart & Vlassis [
The key component is the nice properties of Dirichlet distribution. Let us have one discrete random variable V which can take values from 1 up to K with probabilities (θ1,θ2, ...θK ), where ∑i θi = 1.
The usual way to estimate these parameters in Bayesian statistics is to compute the posterior when assuming that the prior follows dirichlet distribution. Its density is given by D(θ ; n) = B(1n) ∏i θini−1, where θ = { θi} i, n = { ni} i are some hyperparameters and B(n) is a constant depending on them which makes the distribution sum to one. It is known as multinomial beta function.
The prior distribution which states that we have no evidence is expressed by setting all hyperparameters ni equal to 1. It can be interpreted as evidence that all values were observed exactly once or it can be thought of only as smoothing the posterior.
The posterior probability that the variable V contains value i is then equal to proportion of how many times was value i observed.
P(V = i) =
ni . ∑i ni (3)
In the fully observable environment then we could estimate all parameters in the whole structure by (3). We would use this estimate for each state variable X and for each combination of values of its parents paGX . That is the reason why we add X as a lower index to θ and paGX as an upper index to θ as in (1).
Each set of parameters θXpaGX sums to one.
From now on θ without any indexes will denote all these sets of parameters together.
In this simplified case when the whole history was observed the density of probability of being in "information state" θ is
∏ X,paGX
D(θXpaGX ; npXaGX )
The problem that not all state features are observable
can be overcome by the following theorem proven by
Poupart and Vlassis [
Theorem 1. If the prior is a mixture of products of Dirichlets b(s,θ ) = ∑ ci,s i
D(θXp′aGX′ ; npXa′,Gi,Xs ′ ) (4) then the posterior is also a mixture of products of Dirichlets ba,o′ (s′,θ ) = ∑ c j,s′ j
D(θXp′aGX′ ; npXa′,GjX,s′′ ).
Because the proof of the theorem 1 actually gives us the algorithm to update the belief we repeat the proof in this article but for better readability we split it in two lemmas.
The first lemma is technical observation which says that multiplication by θXpaGX only scales the Dirichlet distribution.
Lemma 1. Let θ = (θ1, ...θK ) and n = (n1, ..., nK ) then θ jD(θ ; n) = cD(θ ; m) for some constant c and vector m.
Proof.
θ jD(θ ; n) = = = =
1 B(n) θ j ∏θini−1 =
i 1
∏θini−1+[i== j] = B(n) i B(n + δ )
B(n) n j ∑iK=1 ni
D(θ ; n + δ ) = D(θ ; n + δ ) ing that B(n) = ∏Γ(iK∑=1i=Γ1(nnii)) .
K where δ = (0, ...1, ...0) is a vector of zeroes with one in j-th position.
The last equality follows from the property of B(n) sayLemma 2. P(s′| s, a,θ )b(s,θ ) is mixture of products of Dirichlets. b(s,θ ) in the formula (5) is replaced by its the definition. Then formula (6) is received by switching the terms. Moreover thanks to lemma 1 θ (s′,a,s)PA X can be X consumed by dirichlet distribution D(θXpaX ; n′pXa,iX,s) where paX = (s′, a, s)PA X .
Let c and δ be the as in lemma 1. ci,s must be multiplied by c. That is why it was replaced by cis,′s = c · ci,s in equation (7).
when paX = (s′, a, s)PA X and n′pXa,iX,s = npXa,iX,s + δ n′pXa,iX,s = npXa,iX,s otherwise.
Proof of Theorem 1.
ba,o′ (s,θ ) = kδ (s′O′ = o) ∑ P(s′| s, a,θ )b(s,θ ) s
P(s′| s, a,θ )b(s,θ ) is mixture of products of Dirichlets by lemma . Hence ∑s P(s′| s, a,θ )b(s,θ ) is also mixture of products of dirichlets which are closed under multiplication by constant. It follows that ba,o′ (s,θ ) is mixture of products of dirichlets.
Theorem 1 implies that the belief b(s,θ ) over state s and information state θ can be maintained in a closed form. But how can we from this representation get the probability of being in a specific state? We show in the following theorem that this can be easily done.
Theorem 2. θ in formula (4) for the mixture of products of dirichlet can be integrated out in a closed form.
D(θXp′aGX′ ; npXa′,Gi,Xs ′ )dθ =
D(θXp′aGX′ ; npXa′,Gi,Xs ′ )dθ =
The first equation defines symbol b(s). The second follows from the definition of b(s,θ ) by switching sum and integral. The third equation switches integral and multiplication which is possible in this case because each factor depends on the different variable of multidimensional integration. Density of all probability distributions (including Dirichlet distribution) integrates to one and product of ones is one. That is why the last equation holds.
Despite this encouraging results the number of components in the mixture grows exponentially. Luckily the belief can be approximated by the approximation proposed by Poupart & Vlassis. This will be described in section 7. Firstly, in the next section, we describe the way the belief over possible structures is maintained. 5
The simplest and most naive approach to maintaining the overall belief which contains the probability of structure, its parameters and state would be straightforward. It is sufficient to keep the belief for each structure and probability of the structure. The problem is that the number of graphs on given number of vertices grows very fast with the increasing number of vertices but we want to maintain only the small number of graphs.
We propose to remember only one randomly chosen structure where the probability that the structure G is chosen would be proportional to the probability P(G| history).
The probability P(G| history) could be difficult to
compute. But, as Ross & Pineau noted in article [
The Metropolis-Hastings algorithm needs to use P(history| G) which can be computed as follows: It is equal to P(o| a, b, G) · P(ht−1| G), where ht−1 denotes history up to previous time step.
Then the idea of computing P(o′| a, b) is as follows: P(o′| a, b) is equal (9) to sum of P(s′| a, b) over states s′ compatible with observation o′ and P(s′| a, b) can be computed directly from hyperparameters. For the simplicity of notation we omit conditioning on G.
More precisely it is as follows:
Z ∑ ∑ s′∈S s θ s′O=o′ ∑ ∑ ∑ cis,′s s′∈S s i s′O=o′
P(s′| a, s,θ )b(s,θ )
(9) (10) (11)
Conditioning on b can be replaced as in (10). P(s′| a, s,θ )b(s,θ ) in formula (10) is a mixture of products of dirichlets by lemma 4. Hence by theorem 2 it can be replaced by sum of coefficients as in 10.
The algorithm for belief update is given in algorithm 2 where q(G′| G) is the probability of transition from graph G to graph G′. This distribution can be set any arbitrary way which will ensure that all graphs are reachable. P(G) is prior distribution over graph structures and the probability P(history| G′) can be computed as described above.
Random transitions with probability min 1, PP((hhisisttoorryy|G|G′))PP((GG)′)qq((GG′|′G|G)) are well known under the name Metropolis-Hastlings algorithm. This algorithm ensures that the Markov chain of graphs converges to the distribution P(G| history) which implies that our algorithm eventually learns either the correct structure or a structure with is equally good with respect to encountered history.
One possible way of implementing random changes and distribution q(G′| G) is local change of the graph structure which can include deleting, reversing or adding edge. If the change would be local affecting only limited number of variables then necessary changes to representation of ba,o will be also local.
This change depends on distribution q(G′| G) and isnt’ explicitly written in algorithm 2. We assume that this change is done on the line G := G′ which changes the structure.
Data: belief b (containing structure G and belief for that given structure), action a, observation o Result: representation of belief for the next time step G’ := random modification of G; With a probability min 1, PP((hhisisttoorryy|G|G′))PP((GG′))qq((GG′|′G|G))
G:=G’; b := ba,o; Simplify representation of b by an approximation from section 7.
Final change of belief inside one given structure b := ba,o can be done as in theorem 1. This change includes the changes of coefficients ci,s and hyperparameters npXa′,Gi,Xs ′ . The changes are described in the proof of theorem 1 and associated lemmas. 6
Which action should the agent choose? It should choose the action which maximizes his expected reward with respect to the probability distribution b(s) over the states. This expected reward can be tractably estimated by a recursive approach using depth limited Monte Carlo search.
The algorithm for each action samples several new states. Each sampled state s is then restricted to the observation and then used to update the belief. Its value can be then again estimated by the same algorithm using recursion up to some maximum depth.
This generates sampled walks(series of states) of equal length. Their rewards are summed and in the maximum depth some simple estimate V (b) of the value of belief b is added to the estimate eg. V (b) = ∑s b(s)reward(s) where reward(s) = ∑R∈R sR.
At each level of recursion is the best action chosen. For clarity this Monte Carlo search is shown in algorithm 3.
Data: belief b, depth d Static variable: the number of samples N Result: utility estimate of belief state and selected action if d = 0 then
return V (b); maxQ := - ∞; forall the actions a ∈ A do
Q := 0; for i=1 to N do s′ := sampleState(ba); o′ := s′O; b′ := updateBelief(b, a, o); Q+= (reward(s′)+ +γ · selectAction(b′, d − 1).utility)/N; if Q > maxQ then maxQ := Q; selectedAction := a; return (maxQ,selectedAction);
Data: b(s) Result: sampled state s return state sampled according to weights ∑i ci,s Firstly, it draws a graph according to graph posterior. Then it randomly draws a state with probabilities ∑i ci,s. Which is correct as can be seen thanks to theorem 2.
As noted in section 4 the number of components of the mixture representing current belief for a given graph grows exponentially with time which is untraceable. Each component of the mixture is associated with coefficients ci,s. Naturally some of these coefficients will be smaller while the others will be bigger. We propose to handle this approximately and keep only some components with bigger coefficients.
There are several possibilities: 1. Keep k components with the greatest coefficients. 2. Sample k components with coefficients used as a probability. 3. Instead of generating a lot of components and the sampling only k of them one can directly generate only these randomly chosen components.
For a more detailed description of these and other
approximations along with some of their advantages and
disadvantages we encourage the reader to read [
This article has shown the design of an agent. The agent can be placed to an unknown partially observable environment and it can learn its dynamics by interaction with it. During the interaction it takes into account the exploration-exploitation trade-off and chooses a near optimal action. The dynamics of the environment learnt by our agent is represented by a dynamic Bayesian network which structure is also learnt by our model.
The algorithm could at any time return the graph of dynamic Bayesian network it is currently maintaining as the estimate of the real structure.
This article has shown a possible way of combining known techniques of reinforcement learning of structure of MDP and parameters of POMDP in order to learn both the structure and parameters of POMDP simultaneously.
I am currently implementing and testing the proposed
algorithms. One thing I am going to test is the
alternative representation of belief over possible structures. We
proposed to maintain one Markov chain of possible graph
structures. Alternatively algorithm could maintain several
such Markov chains. It could lead to the possibility of
more precise decisions. Another alternative is to use a
particle filter [