final-hmm-vpi

2 Particle Filtering Apprenticeship We are observing an agent’s actions in an MDP and are trying to determine which out of a set { π 1 , . . . , π n } the agent is following. Let the random variable Π take values in that set and represent the policy that the agent is acting under. We consider only stochastic policies, so that A t is a random variable with a distribution conditioned on S t and Π. As in a typical MDP, S t is a random variable with a distribution conditioned on S t − 1 and A t − 1 . The full Bayes net is shown below. The agent acting in the environment knows what state it is currently in (as is typical in the MDP setting). Unfortunately, however, we, the observer, cannot see the states S t . Thus we are forced to use an adapted particle filtering algorithm to solve this problem. Concretely, we will develop an efficient algorithm to estimate P (Π | a 1: t ). (a) The Bayes net for part (a) is Π s t − 1 s t s t +1 a t − 1 a t a t +1 · · · · · · · · · · · · (i) Select all of the following that are guaranteed to be true in this model for t > 3: □ S t ⊥⊥ S t − 2 | S t − 1 □ S t ⊥⊥ S t − 2 | S t − 1 , A 1: t − 1 □ S t ⊥⊥ S t − 2 | Π □ S t ⊥⊥ S t − 2 | Π , A 1: t − 1 □ S t ⊥⊥ S t − 2 | Π , S t − 1 □ S t ⊥⊥ S t − 2 | Π , S t − 1 , A 1: t − 1 □ None of the above We will compute our estimate for P (Π | a 1: t ) by coming up with a recursive algorithm for computing P (Π , S t | a 1: t ). (We can then sum out S t to get the desired distribution; in this problem we ignore that step.) (ii) Write a recursive expression for P (Π , S t | a 1: t ) in terms of the CPTs in the Bayes net above. P (Π , S t | a 1: t ) ∝ We now try to adapt particle filtering to approximate this value. Each particle will contain a single state s t and a potential policy π i . (iii) The following is pseudocode for the body of the loop in our adapted particle filtering algorithm. Fill in the boxes with the correct values so that the algorithm will approximate P (Π , S t | a 1: t ). 1. Elapse time: for each particle ( s t , π i ), sample a successor s t +1 from . The policy π ′ in the new particle is . 2. Incorporate evidence: To each new particle ( s t +1 , π ′ ), assign weight . 3. Resample particles from the weighted particle distribution. (b) We now observe the acting agent’s actions and rewards at each time step (but we still don’t know the states). Unlike the MDPs in lecture, here we use a stochastic reward function, so that R t is a random variable with a distribution conditioned on S t and A t . The new Bayes net is given by 3