Intro - Lectures 1 and 2

Question 1

What are the three types of machine learning and how are they structured/represented?

Answer 1

Supervised Learning - Function approximation; given y = f(x), find y given x
Unsupervised Learning - Clustering or description; find f in f(x)
Reinforcement Learning - Superficially looks like supervised learning; a method for decision making. Instead of having x and y are given some other value z and need to learn y and f for y = f(x)

Question 2

What are the components of a Markov Decision Process and some forms they can take?

Answer 2

States: S
Model: T(s,a,s') ~ Pr(s' | s,a)
Actions: A(s), A
Reward: R(s), R(s,a), R(s,a,s')
Policy: Pi(s) -> a

Question 3

What is the Markovian property?

Answer 3

Only the present matters. Your next state is only dependent on your current state (how you got there doesn’t matter)

Question 4

How can you get around the Markovian property when past actions/states do matter?

Answer 4

Include all necessary/relevant past information in the current state

Question 5

What is the solution to an MDP?

Answer 5

The policy function, maps states to actions, Pi(s) -> a

Question 6

What is the MDP policy Pi*

Answer 6

Pi* is the optimal policy to maximize long-term rewards

Question 7

What is the difference between planning and RL policy?

Answer 7

Planning aims to develop a concrete (multi-action) plan to achieve an objective. RL policy asks “in each state what action should I take now?”

Question 8

What is one issue with delayed rewards in MDPs? Hint this problem has a name.

Answer 8

Minor changes matter and we must determine which states and actions resulted in the outcomes we saw. This is referred to as the (temporal) credit assignment problem.

Question 9

What assumptions are made in the sequence of rewards for MDPs?

Answer 9

Infinite horizon (stationarity)
Utility of sequences e.g. if
U(s0,s1,s2,…) > U(s0,s’1,s’2,…) then
U(s1,s2,…) > U(s’1,s’2,…)

Question 10

What is the purpose of gamma in an MDP

Answer 10

Gamma is the discount rate [0.0, 1.0) and used to guarantee convergence of the infinite sequence of rewards

Question 11

What is the bounded sum of rewards for an MDP given the max reward R_max and the discount rate gamma?

Answer 11

R_max/(1-gamma)

Question 12

What is the difference between utility and reward?

Answer 12

Utility is based on the long term expected value of an action
Reward is the immediate impact from making an action

Question 13

What is the Bellman equation?

Answer 13

The Bellman equation describes the utility of a state in a discounted MDP

U(s) = R(s) + gamma * max_a Sum_s’ [T(s,a,s’)U(s’)]

Question 14

How can we solve Bellman’s equation directly?

Answer 14

Value Iteration, Policy Iteration

Question 15

How do you perform value iteration?

Answer 15

Start with arbitrary utilities
Update utilities based on neighbors using Bellman’s equation
Repeat until convergence

Question 16

How do you perform policy iteration?

Answer 16

Start - Initialize an arbitrary policy Pi_0
Evaluate - For a timestep t given Pi_t calculate U_t using Bellman’ equation which gives n equations in n unknowns
Improve - Pi_t+1 = argmax_a Sum[T(s,a,s’)U_t(s’)]

Question 17

Compare policy iteration to value iteration

Answer 17

Policy iteration is more expensive per iteration (matrix inversion of nxn matrix) but may require less iterations
Both are guaranteed to converge

Question 18

What is the relationship between the three forms of the Bellman equation?

Answer 18

Watch Lession 1.29

Question 19

In a RL context the agent acts as ___ and the environment acts as ___

Answer 19

policy (pi); the MDP

Question 20

What types of behavior can AI agents learn?

Answer 20

Plan - Fixed sequence of actions (stochasticity causes problems)*
Conditional Plan - A plan with if/else statements (can handle some stochasticity)
Stationary Policy/Universal Plan - Mapping from state to action for every state (can handle any stochasticity, but very large)

*Dynamic replanning - Recreate a new plan if something goes wrong

Question 21

How do we evaluate a learner?

Answer 21

1. Value of returned policy
2. Computational complexity (how much time needed)
3. Experience/sample complexity (how much data needed)