Inverse Reinforcement Learning in Partially Observable Environments

1 Introduction

The goal of inverse reinforcement learning (IRL) is to determine the reward function that an agent is optimizing given the agent's behaviour over time [Russell, 1998]. Existing IRL algorithms (e.g., Ng and Russell [2000], Ramanchandran and Amir [2007], and Ziebart et al. [2008]) mostly assume that the agent acts in an environment which can be modeled as a Markov decision process (MDP).

Although the MDP assumption provides a good starting point for developing IRL algorithms, the implication is that the agent has access to the true, global state of the environment. The assumption of an omniscient agent is often too strong in practice: even though the agent is assumed to be an expert in the given environment, the agent may be (and often is) making optimal behaviour with a limited sensory capability. Hence, it calls for an extension of IRL algorithms to partially observable environments.

In this paper, we present an IRL algorithm for partially observable environments. Specifically, we assume that the environment is modeled as a partially observable Markov decision process (POMDP), and try to compute the reward function given that the agent follows an optimal policy. Our algorithm is mainly motivated by the classical IRL algorithm by Ng and Russell [2000]. We believe that some of the more recently proposed IRL algorithms could also be extended to handle partially observable environments. The point of this paper is to show the general framework for dealing with partially observable environments, the computational challenges involved in doing so, and some approximation techniques for coping with the challenge.

We believe that our work will prove useful for many problems that could be modeled as POMDPs. For example, the current practice in developing POMDP-based dialogue systems for speech interfaces [Williams and Young, 2007] mostly relies on a labor intensive process: the balance among the reward of a successful dialogue, the penalty of an unsuccessful dialogue, and the cost of information gathering is manually adjusted until a satisfying dialogue policy is obtained from the POMDP. Our work could serve as a foundation for automating the reward specification process (e.g., using the dialogue corpus collected from a wizard-of-oz study) and transferring the reward function to a different dialogue domain (e.g., almost identical reward structure for the travel reservation domain and the appliance control domain).

2 Preliminaries

In this section, we briefly review some of the notations and definitions regarding the models for sequential decision making under uncertainty, namely MDPs and POMDPs. We also briefly overview the IRL algorithm by Ng and Russell [2000] for the sake of presentation of our work.

2.1 MDPs and POMDPs

A Markov decision process (MDP) is defined as a tuple 〈S,A, T,R, γ〉: S is the finite set of states; A is the finite set of actions; T is the state transition function where T (s, a, s′) denotes the probability P (s′ |s, a) of changing to state s′ from state s by taking action a; R is the reward function where R(s, a) denotes the immediate reward of executing action a in state s, whose absolute value is bounded by Rmax; γ ∈ [0, 1) is the discount factor.

A policy is defined as a mapping π : S → A. The value function of policy π is the expected discounted return of executing the policy in the state s:

Given an MDP, the agent's objective is to find an optimal policy π∗ that maximizes the value for all the states, which should satisfy the Bellman equation:

It is often useful to express the above equation in terms of Q-function: π is an optimal policy if and only if

whereQπ

The partially observable Markov decision process (POMDP) extends MDP for the agent's noisy observation of the environment. A POMDP is defined as a tuple 〈S,A, Z, T,O,R, b0, γ〉: S,A, T,R and γ are defined the same as in MDPs; Z is the finite set of observations; O is the observation function where O(s, a, z) denotes the probability P (z|s, a) of perceiving observation z when executing action a and arriving in state s; b0 is the initial state distribution where b0(s) denotes the probability of starting in state s.

Since the true state is hidden, the agent has to act based on the history of executed actions and perceived observations. Hence, a policy in POMDP is defined as a mapping from action-observation histories to actions. Since the number of possible histories grows exponentially in the number of time steps, many POMDP algorithms use the concept of belief. Formally, the belief b is the probability distribution over the current states, where b(s) denotes the probability that the state is s at the current time step. The belief update for the next time step can be computed from the belief at the current time step: given the action a at the current time step and the observation z at the next time step, the updated belief baz for the next time step is obtained by

where P (z|b, a) = ∑s′ ∈S O(s′ , a, z) ∑s∈S T (s, a, s′)b(s). Hence, the belief serves as a sufficient statistic for fully summarizing histories, and the policy can be equivalently defined as a mapping from beliefs to actions. Using beliefs, we can view POMDPs as belief-state MDPs, and the value function of an optimal policy satisfies the Bellman equation

Alternatively, a policy in POMDP can be represented as a finite state controller (FSC). An FSC policy is defined by a directed graph 〈N, E〉, where each node n ∈ N is associated with an action a ∈ A and has an outgoing edge ez ∈ E per observation z ∈ Z. The policy can be denoted as π = 〈ψ, η〉 where ψ is the action strategy associating each node n with action ψ(n) ∈ A, and η is the observation strategy associating each node n and observation z with a successor node η(n, z) ∈ N .

Given an FSC policy π, the value function V π is defined over the joint space of FSC nodes and POMDP states: for node n and state s,

where

with a = ψ(n) and os(z) = η(n, z). The value at node n for belief b is calculated by

and the starting node for the initial belief b0 is chosen by n0 = argmaxn V π (n, b0). We can also define Q-function for an FSC policy π:

which is the expected discounted return of choosing action a at node n and moving to node os(z) upon observation z, and then following policy π. Also the Q-function for node n at belief b is computed by

With an FSC policy π, we can sort the reachable beliefs into nodes, so that Bn denotes the set of beliefs that are reachable when the current node is n. Note that |Bn| ≥ 1 for every node n.

2.2 IRL for MDP\R

Formally, the inverse reinforcement learning (IRL) problem in completely-observable Markovian environments is stated as follows: Given an MDP\R 〈S,A, T, γ〉 and an expert's policy π, find the reward function R that makes π an optimal policy for the MDP.

Ng and Russell [2000] present a necessary and sufficient condition for the reward function R of an MDP to guarantee the optimality of π:

which states that deviating from the expert's policy should not yield a higher value. This condition can be equivalently reformulated in terms of R:

where Ta denotes the |S| × |S| matrix with the element (s, s′ ) being the transition probability T (s, a, s′) and Rπ(s) denotes the |S| vector with the s-th element being the reward R(s, π(s)).

Given the expert's policy π, which is assumed to be optimal, the reward function is found by solving the optimization problem:

subject to Constraint (7) and

where λ is an adjustable weight for the penalty of having too many non-zero entries in the reward function. The idea is to maximize the sum of margins 1 between the expert's policy and all other policies, in the hope that the expert's policy is optimal while favoring the sparseness in the reward function.

1 We found it more successful to use the sum-of-margins approach than the minimum-of-margins approach in the original paper, since the latter fails when there are multiple optimal policies.

When the expert's policy is not explicitly given but instead the trajectories of the expert's policy in the state and action spaces are available, the algorithm starts with a "base case" random policy π1. Ideally, the true reward function R should yield V ∗ (s) ≥ V π1 (s) since π∗ is an optimal policy with respect to R. For a candidate reward function ˆR, the value of π∗ for the starting state s0 is estimated by the average empirical return:

where {sm0 , sm1 , · · · , smT-1} and {am0 , am1 , · · · , amT-1} are the T -step state and action sequences in the m-th trajectory of the expert's policy. The values of other policies with candidate reward function ˆR are either estimated by sampling trajectories or exactly computed by solving the Bellman equation.

The algorithm iteratively tries to find a better reward function ˆR, given the set of policies found by the algorithm Π = {π1, . . . , πk} up to iteration k, by solving the following optimization problem:

where p(x) = x if x ≥ 0, and p(x) = 2x if x < 0. The algorithm then computes a new policy π′ that maximizes value function under the new reward function, and add π′ to Π. The algorithm continues until it has found a satisfactory reward function.

3 IRL in Partially Observable Environments

In this section, we present our IRL algorithms for partially observable environments. Formally, given an POMDP\R 〈S,A, Z, T,O, b0, γ〉 and an expert's policy π, we seek the reward function R that makes π an optimal policy for the POMDP. As in IRL for MDP\R, the expert's policy can be given either explicitly in the form of FSC or implicitly by the sampled trajectories of beliefs.

3.1 IRL for POMDP\R from FSC Policies

One of the most natural ways to specify a policy for POMDPs is to use the FSC representation. Hence, when the expert's policy is explicitly given, we will assume that it is represented in the form of an FSC.

We could derive a simple and naive condition for the optimality of the expert's policy, by assuring that the action and observation strategies are optimal at every node, analogous to Equation (6). Given an expert's policy π = 〈ψ, η〉,

for every node n in π. This inequality states that any policy that deviates from the expert's action and observation strategies should not yield a higher value than that of π. Since it is infeasible to check the value for all possible beliefs, we approximate the condition by comparing the values only for the sampled beliefs reachable by the expert's policy.

However, Equation (8) is not a sufficient condition for the optimality of π: not only we want to compare to the policies with different action and observation strategies, but we also want to take into account other policies that have different number of nodes compared to π, including policies with an infinite number of nodes! Since it is clearly infeasible to include all possible FSC policies into the inequality, we have to resort to a subset of policies that provide a useful feasible region of the reward function. For example, Equation (8) uses the set of |N||A||N||Z| policies that have the same (and possibly fewer) number of nodes as the expert's policy.

A more sound approach to defining the set of policies is to use the set of FSC policies that arise during the dynamic programming update of the expert's policy [Hansen, 1998]. Given the expert's policy π, the dynamic programming update generates |A||N||Z| new nodes for all possible action and observation strategies, and these nodes can potentially be a new starting node. This idea comes from the generalized Howards' policy improvement theorem [Howard, 1960]:

Theorem 1 If an FSC policy is not optimal, dynamic programming update transforms it into an FSC policy with a value function that is as good or better for every belief state and better for some belief state.

Hence, if the value does not improve for any belief by the dynamic programming update, the expert's policy should be optimal. We should proceed with caution however in the sense that the dynamic programming update does not generate all the necessary nodes to guarantee the optimality of the expert's policy: the nodes in the expert's policy are only those reachable from the starting node n0, which yields the maximum value at initial belief b0. Nodes that yield the maximum value at some other belief (i.e., useful) but not reachable from n0 are not present in the expert's policy. To guarantee the optimality of the expert's policy, we need to include those non-existent but useful nodes in the dynamic programming update, but since there is no way to recover them, we settle for using only the nodes in the expert's policy.

Formally, for the set of newly generated nodes Nnew, the value function of node nnew ∈ Nnew with action strategy of selecting action a and observation strategy os is given by

where V π is the value function of the expert's policy calculated from Equation (2). Note that V new as well as V π are linear in terms of R. Now, the value function of policy π should satisfy

for every node n ∈ N in order to guarantee the optimality of the expert's policy π.

A more computationally efficient way to generate the set of policies is to use the witness theorem [Kaelbling et al., 1998]. Re-stated in terms of FSC policies, we have the following:

Theorem 2 Let Ua be a nonempty set of useful nodes with the action strategy of choosing action a, and N a be the complete set of useful nodes with the action strategy of choosing action a. Then Ua ̸= N a if and only if there is some node ˜n ∈ Ua, observation z, and n′ ∈ N for which there is some belief b such that

for all n ∈ Ua, where nnew is a node that agrees with ˜n in its action and all its successor nodes except for observation z, for which η(nnew, z) = n′ .

The witness theorem tells us that if we generate all possible nnew's by changing the successor node of each single observation and check the value for all possible beliefs, we can guarantee the optimality of π. This leads us to the same inequality constraint as Equation (10), except that Nnew is defined in a different way. For each action a, we prepare Ua = {n ∈ N|ψ(n) = a} and use the witness theorem to generate |N|2 |Z| new nodes. We then use the dynamic programming update to generate |A-N ||N||Z| additional nodes, where A-N is the set of actions that is not selected at any of the nodes in N. Hence, using the witness theorem, we have |Nnew| ≤ |N|2 |Z| + |A-N||N||Z| , often much fewer compared to those generated by only using the dynamic programming update.

Let us now turn our attention to the complete optimization problem. If we use the optimality constraint in Equation (8), we would like to maximize the sum of margins between the expert's policy and other policies, while making the reward function as sparse as possible:

If we use the dynamic programming update or the witness theorem, the policies other than the expert's policy are captured in nnew's, hence the optimization problem now becomes:

where Nnew is the set of nodes generated by the dynamic programming update, or by the witness-based method.

3.2 IRL for POMDP\R from Sampled Trajectories

In many cases, the expert's policy may not be explicitly given, but the set of trajectories may be available instead. Here, we assume that it is the set of T -step belief trajectories, where the m-th trajectory is denoted by {bm0 , bm1 , . . . , bmT-1}. If the observation trajectories {zm 0 , zm 1 , . . . , zm T-1} and the action trajectories {am0 , am1 , . . . , amT-1} are available instead, we can reconstruct the belief trajectories by using the belief update in Equation (1).

In order to derive an IRL algorithm for POMDP\R from the sampled belief trajectories, we make the same assumption as in Ng and Russell [2000] about the reward function

where φ1, . . . , φd are the known basis functions mapping from S × A to ℜ, and the αi's are the unknown parameters.

Choose a number of beliefs bj , j = 1, . . . , J. Choose a random initial policy π1, and set Π = {π1}.

for K

= 1 to MaxIter

Find ˆαi's by solving the linear program:

Find πK+1 that is optimal w.r.t. the reward function

ˆR(s, a) = ˆα1φ1(s, a) + ˆα2φ2(s, a) +

if V πK+1

(bj )

- ˆ

V π

· · ·

+ ˆαdφd(s, a)

(bj) ≤ ϵ, ∀j then return ˆR

else Π = Π ∪ {πK+1}

return ˆR

Figure 1: IRL for POMDP\R from the sampled trajectories.

The reward for belief b is then calculated by

where φi(b, a) = ∑s b(s)φi(s, a). We also define ˆ V π i (bm0 ) to be the average empirical return of the m-th trajectory when using each basis function as the reward function (R = φi)

so that we have

Noting that bm0 = b0 for all m, the average empirical return at b0 is given byˆ

which is linear in terms of α1, . . . , αd.

Given the definitions above, the rest of the derivation is fairly straightforward, and leads to a similar algorithm to that of Ng and Russell [2000], shown in Figure 1. The algorithm iteratively tries to find a reward function parameterized by αi's that maximizes the sum of the differences between the ˆ V π of the expert's policy and V πk of each FSC policy πk ∈ Π found so far. The differences in the values are measured at the representative beliefs bj's, which are chosen if they appear frequently in the early time steps of the trajectories, ensuring low estimation error in the values. We could use the initial belief b0 as the only representative belief (similar to Ng and Russell [2000] using only s0), but we found it more effective in our experiments to include additional beliefs since they often provide a better guidance in the search of the reward function by tightening the feasible region. The average empirical return of the expert's trajectories at the representative belief bj is computed by

where T m j is the first time that bj is found in m-th trajectory and Mj is the number of trajectories that contain bj. However, computing V πk (bj) is not well defined since bj may be unreachableunder πk. In ourwork, we use an upperboundapproximation V πk (bj ) ≈ maxn V πk (n, bj ), where V πk (n, bj ) is computed by Equation (3).

When πK+1 = π, the differences in the value function for all representative beliefs will vanish. Hence, the algorithm terminates when all the differences in the values are below the threshold ϵ, or the iteration number has reached the maximum number of steps MaxIter.

4 Experiments

The first set of experiments concerns with the case when the expert's policy is explicitly given using the FSC representation. We chose three POMDP problems for the experiments: Tiger, 1d maze, and 5 × 5 grid world. The tiger and the 1d maze problems are classic benchmark problems in the POMDP literature, and their specifications can be found in [Cassandra et al., 1994]. The 5 × 5 grid world problem is inspired by the one in [Ng and Russell, 2000], where the agent can move west, east, north or south, and their effect is assumed to be deterministic. The agent always starts from the north-west corner of the grid and aims to reach the goal in the south-east corner. The current position cannot be observed directly but the presence of the walls can be perceived without any noise when the agent is on the border of the grid. Hence, there are nine observations, eight of them corresponding to eight possible configurations of the nearby walls when on the border, and one corresponding to no wall observation when not on the border. The optimal policies for the problems were computed using PBPI [Ji et al., 2007], and used as the expert's policies.

We experimented with all three approaches in Section 3.1: the Q-function based approach, the DP-update based approach, and the witness theorem based approach. As in the case of IRL for MDP\R, we were able to control the sparseness in the reward function by tuning the penalty weight λ. With the suitable value for λ, all three approaches yielded the same reward function. The estimated reward function is compared to the true reward function in Figure 2 for the tiger and 1d maze problems, and in Figure 3 for the 5 × 5 grid world problem. We discuss each result below.

In the tiger problem (top of Figure 2), the true reward function is not sparse since every action is associated with a nonzero reward. Since our methods favor sparse reward functions, there is some degree of difference between the true and the learned reward functions, most notably for the listen action, where our methods assign zero reward instead of -1 as in the true reward. However, we can apply the policyinvariant reward transformation [Ng et al., 1999] on the true reward function so that listen action yields zero reward. The learned reward function is very close to the transformed one, as shown in the figure.

In the 1d maze problem (bottom of Figure 2), the expert's policy has three nodes: node n0 (the starting node) chooses to move right, and changes to node n1 upon observing nothing or to node n2 upon observing goal; node n1 chooses to

move right and always changes to node n2; node n2 chooses to move left, and changes to node n0 upon observing nothing or to itself upon observing goal. If we follow the expert's policy, the probability of moving right is larger than that of moving left in the left and middle states. Furthermore, the probability of moving right in the middle state is larger than that of moving right in the left state. Hence, the algorithm assigns negative rewards for moving left in the left and middle states, and even a lower reward for the middle state than that for the left state. However, the optimal policy from the POMDP with the learned reward function is the same as the expert's policy.

Finally, in the 5 × 5 grid world problem (Figure 3), the expert's policy is very simple: the agent moves east until it observes the north-east corner, and moves south until it observes the south-east corner. In the figure, the states are numbered sequentially from the start state, so that state 0 corresponds to the north-west corner, state 4 corresponds to the north-east corner, and state 24 corresponds to the south-east corner. Our methods assign positive reward for moving east in the goal state, and zero or negative reward for all other pairs of state and action. Again, even though the learned reward function is different from the true one, it yields the same optimal policy.

The second set of experiments is for the case when the expert's trajectories are given. We experimented on the same set of three problems, with the basis functions chosen as follows: for the tiger and the 1d maze problems, we used the table representation for the reward function, i.e., each pair of state and action as its own basis function; for the 5 × 5 grid world problem, we prepared six basis functions, five for the states in the south border, and one for all other states. We sampled 5000 belief trajectories each of length 50 time steps. In each iteration K of the algorithm (Figure 1), we evaluated πK+1 using the true reward. Figure 4 shows the mean values and the standard deviations of 100 trials on the tiger and the 1d maze problems. For the tiger and the 1d maze problems, our algorithm took an average of 3.91 and 1.97 iterations respectively. The learned reward upon termination yielded the optimal policy in 90% and 98% of the trials for the tiger and the 1d maze problems respectively. The overall average value of the policies was 1.54 for the tiger problem (optimal policy yields 1.93), and 1.19 for the 1d maze problem (optimal policy yields 1.20). We excluded the result on the 5 × 5 grid world problem in Figure 4, since the optimal reward is found in only 1 iteration for all the trials.

5 Conclusion and Future Work

We presented an IRL framework for dealing with partially observable environments. Experimental results on POMDP benchmark domains show that, in most cases, our algorithm robustly finds solutions close to the true reward functions generating exactly the same optimal policy. The presented work is only a demonstration of how the existing body of work on IRL on MDP\R could be extended to POMDP\R, and more recent IRL techniques as well as some of the IRL-based apprenticeship learning techniques could be similarly extended by following our line of thought.

There are a number of challenges that should be addressed in the future. First, the scalability of our methods should be improved, so that we can handle more realistic problems with large policies, such as dialogue management problems with hundreds of policy nodes. Second, it remains as an open problem whether there exists a sufficient condition for optimality and a tractable method exploiting it. Even we use the witness theorem as a non-sufficient condition, we may end up with a huge number of constraints. We could sample from the exhaustive set of conditions, but the theoretical analyses should be accompanied. Third, some of the issues regarding the convergence to suboptimal rewards could be addressed by more recent techniques, such as Abbeel and Ng [2004] and Ramanchandran and Amir [2007].

6 Acknowledgments

This work was supported by Korea Research Foundation Grant KRF-D00527, and by Defense Acquisition Program Administration and Agency for Defense Development of Korea under contract UD080042AD.