Week 4

Question 1

a*

Answer 1

A rational agent chooses the action which maximises its utility

Question 2

Expected utility

Answer 2

For the possible states that arise from action a (s’ € s_a

Question 3

Maxmin criterion

Answer 3

Focus is on choosing action that has least-bad worst outcome

We are maximising the action choose for the best min state

Question 4

Maximax criterion

Answer 4

Choose the action that has the best best case scenario

Question 5

First order Markovian? Second?

Answer 5

Decision only depends on itself, second: depends on decision before

Question 6

Components of a Markov Decision Process (MDP)

Answer 6

• set of states s € S with initial state s₀
• set of actions in each state A(s)
• transition model P(s’|s,a)
• reward function R(s)

Question 7

What is a policy

Answer 7

For MDP, set of actions for each state, e.g;

• π: π(s₀) = left, π(s₁) = right, π(s₂) = forward, …

Question 8

Considerations when calculating Utility of a run

Answer 8

For a run (series of states);
-consider horizon (in)finite
- are utilities (non)stationary (do they change?)

Question 9

Difference between additive and discounted rewards

Answer 9

Question 10

Proper policy

Answer 10

Always ends in a terminal state eventually

Question 11

Problem with infinite horizons?

Answer 11

Could make calculation of expected utility of policy inf

Question 12

How to deal with infinite horizons ?

Answer 12

• proper policies
• average rewards (divide expected utility by # of state)
• discounted rewards

Question 13

Calculate expected utility of run for infinite run

Answer 13

Question 14

Expected utility of a policy π (using discounted rewards)

Answer 14

Where S_t is the RV, state that the agents get to at time t

Question 15

Optimal policy (notation)

Answer 15

Question 16

Policy for Choosing action that maximised expected utility of next state

Answer 16

Question 17

Bellman equation

Answer 17

Utility of state is rewards of state + (discount factor)* max of utility of next state

Question 18

Value iteration process

Answer 18

Continue until values of states don’t change
Guaranteed to converge to optimal

Question 19

Policy improvement

Answer 19

Question 20

Policy evaluation

Answer 20

Question 21

Policy iteration

Answer 21

1) policy evaluation (for every state)
2) policy improvement (for every state)

Until convergence

Question 22

Approximate policy evaluation

Answer 22

Question 23

Modified policy iteration

Answer 23

Question 24

Modified policy iteration pro and con

Answer 24

Pro: way more efficient
Con: not guaranteed to converge

Question 25

Transition model is?

Answer 25

P(s’|s,a)