MDP

Question 1

What’s the formal definition of a Markov Decision Process

Answer 1

A tuple of:

1. S, State space
2. A, Action space
3. P^1_ss’, transition probability matrix, collected at the transition from s to s’
4. gamma, the discount factor
5. R^a_ss’, the immediate reward for leaving state s.
6. pi(a|s) probability for a given s, can also be deterministic.

Question 2

How is the value function for an MDP defined?

Answer 2

V^{pi}(s) = E[R_t | S_t=s]

Question 3

Why is the first term in the MRP value function Rs while the first term of the MDP value function is E[r_t+1 | S_t = s] (expected value)?

Answer 3

The reward function of an MDP depends on the state (s), action (a) and next state(s’). These can be probabilistic, so we have to use the expected value.

Question 4

What’s the unpacked form of V^{pi}(s)

Answer 4

V^{pi}(s) = sum policy(a |s) sum P^a_ss’(R^{a}_ss’ + gamma V^{pi}(s’))

Question 5

Describe the iterative policy evaluation algorithm

Answer 5

initalize V(s) to 0 for all s

repeat:
for each s in S:
V(s) = sum policy(a |s) sum P^a_ss’(R^{a}_ss’ + gamma V^ V^{pi}(s’))
until termination criterion is reached.

Question 6

Describe the difference between synchronous and asynchronous updates in the iterative algorithm

Answer 6

Async updates update the value function for each state continuously, while sync. update calculates all new values before updating the value function.

Question 7

what is the state-action value function, Q^pi(s,a)?

Answer 7

It describes how good it is to take action a in state s given policy pi. It i connected to the (state) value function by:

V(s) = sum pi(s, a) * sum Q^pi(s,a)

Question 8

Does there always exist an optimal policy in MDPS?

Answer 8

Yes, at least one, but there might be more

Question 9

How is an optimal policy defined?

Answer 9

A policy, pi, is optimal if V_pi(s) >= V_pi(s) for all other pi and all states s.

Question 10

What does the belman optimality equation for V state for MDP?

Answer 10

The value of a state under an optimal policy, must be equal to the expected return for the best action in that state.