Journal

MAY 2nd— MAY 8th

MAY 9th— MAY 15th

MAY 16th— MAY 22nd

This week we had an orientation lab meeting with Reasoning and Learning lab members. Some of the students gave presentations on their research activities and what they had done so far. Afterwards we had an introduction of all the members. It was interesting to see around 30 people are working in this lab. Followed by that, Marc gave us some useful information about the lab facilities.

Every Wednesday I’ll have a meeting with our duality teem consisting of

Prakash Panangaden, Joelle Pineau, Doina Precup, Milena Scaccia and I.

To start with, Prakash gave us a paper entitled “The Duality of State and Observations” which I should read during the next week.

This week was spent mainly on reading the “The Duality of State and Observations” paper. The main idea is as follows:

Partially Observable Markov Decision Process (POMDP) is a model for describing planning tasks under uncertainty, where the decision maker doesn’t have complete information about its current state. In this model problems have discrete states and actions. Actions cause stochastic transitions between states, and observations at each step depend on the previous action and the current state.

In this paper a duality theory for POMDPs has been developed. The idea of duality is to interchange the role of states and observations. The double-dual representation has some important aspects:

1. It is deterministic.

2. It has no hidden states.

3. It is minimal.

Before moving on to POMDPs the paper explains the construction of duals for simpler situations like deterministic Kripke automata (DKA). Let K be a DKA with states set S and actions set A. In the dual machine K ‘ the states are the equivalence classes of tests on K, and the observations are the states of K.

Now consider K” (the dual of the dual). Its states are equivalence classes of K’-tests.

There exists a mapping from states of the original automata K to the states of the double dual automata K” called SAT. For any state s in K, SAT(s) is the equivalence classes of K-tests that s satisfies them.

It has been proved in the paper that SAT is a bijection from S to S” when K is reduced (We say that K is reduced if it has no ≡- equivalent states).

The problem that Milena and I should work on during next week is:

“If Sat(s1)=Sat(s2) then what equivalence holds between s1 and s2?”

In other words we are interested to know what relation exists between the states of the original automata when they collapse into one state of the double dual.

Top

To answer the assigned problem of this week, I read a paper entitled “A Hierarchy of Equivalence Relations for Partially Observable Markov Decision Processes” written by Monica Dinculescu. The paper discusses different types of equivalence relations on states. Different types are: “t-equivalent, e-equivalent, trace equivalent and bisimulation”. Then it shows that e-equivalence and trace equivalence are identical. And it proceeds by proving that bisimulation implies e-equivalence, and trace equivalence implies t-equivalence.

Therefore, bisimulation is the strongest equivalence class and t-equivalence is the weakest one.

Our approach to the problem is as follows:

We showed that for both deterministic and non-deterministic automata if Sat(s1)=Sat(s2) then s1 and s2 are t– equivalent. Then we found out that the states in non-deterministic automata cannot have higher relation than t-equivalence, and we proved it by finding a counter example that shows a case in which Sat(s1)=Sat(s2) but s1 and s2 are not e-equivalent. For the deterministic one, we believe that t-equivalence, e-equivalence and bisimulation are all identical because if you know the start state and the sequence of actions then the observations do not provide any additional information, but this needs to be proved.

The questions that we should work on during the next 2 weeks are:

1. Find a map from the states of primal to double-dual in POPAs and then in POMDPs

If such a map exists then call it F:.

2. If F(s1)=F(s2) what equivalence holds between s1 and s2 ?

MAY 23rd— MAY 29th

Top

For finding the map from the states of primal to double-dual in POPAs, I worked on some simple examples and tried to construct their double duals, which helped me to have a better vision of duality concept. In this process I found out that the t-equivalent states of primal collapse into one state in the double dual. I also came up with an example which shows that a simple 2 state POPA has infinite number of states in its dual and double dual representation. This has arisen some questions in my mind, such as:

1. What does it mean that the double dual is minimal when the primal is a finite machine but the double dual is infinite?

2. Should I deal with probabilities to be able to make a map from primal to double dual?

I’m going to discuss these questions in our next meeting.

Milena and I have also proved that in a deterministic automaton bisimulation, e-equivalence and t-equivalence are all identical. The proof for the equivalence of t-equivalence and e-equivalence is by induction on the number of observations. And the proof for the equivalence of e-equivalence and bisimulation is by contradiction.

Dorna Kashef Haghighi

LINKS

CDMP

McGill

School of Computer Science

Week 1-4 | Week 5-8 | Week 9-12 | Week 13-16