reinforcement learning

Question 1

Sequential Decision Making

Question 2

Temporal Credit Assignment problems

Answer 2

• needs sequential action selection to be completed
• has state transitions triggered by actions
• involves delayed rewards based on success / failure

Question 3

Markov Decision Process

Answer 3

states, actions, transition function, reward function
goal is to optimize long-term reward
continuous tasks => return is infinite => need a discount

Question 4

Markov assumption

Answer 4

• the effect of actions depend only on the current state
• means that everything I need to know can be observed, no need to remember anything

Question 5

Sutton & Barto V2

Answer 5

• combine transition (probabilistic) and reward function => dynamic function => probabilistic function
• can be transformed into deterministic function by taking the expect value of function above

Question 6

Policy

Answer 6

• feedback plan, not open-loop plan
• alternate between policy iteration and policy improvement (together called policy iteration)to converge to optimal policy
  Policy evaluation:
• do some iterations (no need to do this until convergence) of computing the Bellman equation for every state according to a deterministic policy
• when computing the value function for a state, we take into account all possible actions
  Policy improvement:
• update the policy according to highest action-value function value for every state (so compute all possible actions for a state and choose the max, do this for all states)
  Extreme Value Iteration:
• do policy evaluation once and combine with policy improvement in one single step
• repeatedly sweep through state space until convergence

Question 7

Model-based RL

Answer 7

observe model, keep track of state transitions, count, compute probabilities for all state transitions, do the same for rewards

Question 8

Model-free RL

Answer 8

estimate value function / q-value function / policy DIRECTLY

Question 9

On-policy RL

Answer 9

learn the value function of the policy that selects the action
behavior generation is coupled to learning V or Q

Question 10

Off-policy RL

Answer 10

convergence of value function is not influenced by actions selected
behavior generation is decoupled from learning V or Q

Question 11

Temporal difference (model-free, on-policy)

Answer 11

• do not use any reward/transition function, only policy
• update value function based on SAMPLED EXPERIENCE
• updated value = old value + learning rate * (reward + temporal difference)
• TD = discounted value of new state - value of old state

Question 12

SARSA (model-free, on-policy)

Answer 12

• fix exploration policy
• update Q function based on this exploration policy (equation very similar to TD)
• after convergence, we have final Q function, which we can use to improve exploration policy
• another approach is to improve exploration policy WHILE updating Q function => epsilon-greedy

Question 13

Q-learning (model-free, off-policy)

Answer 13

update of value function is not influenced by actually selected action
updated value = old value + learning rate * (reward + discount * highest value possible from new state - old value)