W2 MDP & Tabular Value-based

Question 1

What is the 5-tuple of a Markov Decision Process?

Answer 1

(S, A, T_a, R_a, gamma)
S: state space
A: action space
T_a: transition fuction in the environment
R_a: reward
gamma: discount factor representing the difference between future and present rewards.

Question 2

Value-based methods, policy-based methods work well for discrete or continuous spaces?

Answer 2

Value-based: Discrete
Policy-based: Discrete & Continuous

Question 3

Actions & Rewards learning in a tree, which directions?

Answer 3

Actions: downward to the leaves
Rewards: upward, backpropagation to the root

Question 4

what is a sequential decision problem?

Answer 4

the agent has to make a sequence of decisions in order to solve a problem

Question 5

what is the Markov property?

Answer 5

the next state depends only on the current state and the actions available in it (no influence of historical memory of previous states)

Question 6

What is a policy pi(a|s)?

Answer 6

a conditional probability distribution that for each possible state specifies the probability of each possible action.

Question 7

What’s on-policy?

Answer 7

The learning takes place by consistently backing up the value of the selected action back to the same behavior policy function that was used to select the action
SARSA is on-policy

Question 8

What’s off-policy?

Answer 8

the learning takes place by backing up values of another action, not the one selected by the behavior policy
Q-learning is off-policy and it is greedy: backup the value of the best action
convergence in off-policy can be slower, since older, non-current, values are used.

The behavior policy and the target policy are different in Q-learning, but they are the same in SARSA.

Question 9

SARSA update formula? (𝛼=learning rate, 𝛾=discount factor)

Answer 9

𝑄(𝑠𝑡, 𝑎𝑡) ← 𝑄(𝑠𝑡, 𝑎𝑡) + 𝛼[𝑟𝑡+1 + 𝛾𝑄(𝑠𝑡+1, 𝑎𝑡+1) − 𝑄(𝑠𝑡, 𝑎𝑡)]

Question 10

Q-learning update formula?

Answer 10

𝑄(𝑠𝑡, 𝑎𝑡) ← 𝑄(𝑠𝑡, 𝑎𝑡) + 𝛼[𝑟𝑡+1 + 𝛾 max𝑎𝑄(𝑠𝑡+1, 𝑎) − 𝑄(𝑠𝑡, 𝑎𝑡)]

Question 11

In reinforcement learning the agent can choose which training examples are generated. Why is this beneficial? What is a potential problem?

Answer 11

We can generate a endless dataset ourselves, through simulations. But on the other hand, we don’t have the ‘gold standard’ actions given a state, nothing is labeled. We have to derive the correct policy ourselves.

Question 12

What is Grid world?

Answer 12

Grid worlds are the simplest environments, it consists of a rectangular grid of squares, with a start square, and a goal square.

Question 13

In a tree diagram, is successor selection of behavior up or down?
In a tree diagram, is learning values through backpropagation up or down?

Answer 13

Learning up

Selecting down

Question 14

What is 𝜏?
What is 𝜋(s)
What is 𝑉(𝑠)?
What is 𝑄(𝑠, 𝑎)?

Answer 14

𝜏: Trace, a full rollout of a simulation.
𝜋(s): the policy function answers the question how the different actions 𝑎 at state 𝑠 should be chosen
𝑉(𝑠): The expected cumulative discounted future reward of a state
𝑄(𝑠, 𝑎): Q-value estimate, estimated value of taking action 𝑎 in state 𝑠

Question 15

What is dynamic programming?

Answer 15

In the context of RL, in Dynamic Programming we recursively traverse the state space. An example algorithm is Value-iteration.

Question 16

What is recursion?

Answer 16

Calling the same code segment within that code segment.

Question 17

Do you know a dynamic programming method to determine the value of a state?

Answer 17

Value-iteration: it repeatedly updates 𝑄(𝑠, 𝑎) and 𝑉(𝑠) values, looping over the states and their actions, until convergence occurs.

Question 18

Is an action in an environment reversible for the agent?

Answer 18

No, just like in the real world, there is no undo.

Question 19

Is the action space of games typically discrete or continuous?
Is the action space of robots typically discrete or continuous?
Is the environment of games typically deterministic or stochastic?
Is the environment of robots typically deterministic or stochastic?

Answer 19

Discrete
Continuous
Deterministic
Stochastic

Question 20

What is the goal of reinforcement learning?

Answer 20

to find the sequence of actions that gives the highest reward, or, more formally, to find the optimal policy that gives in each state the best action to take

generally, the objective is to achieve the highest possible average return from the start state

find the optimal policy pi*(a|s) = argmax V^pi (s_0), so for start state s_0

Question 21

Which of the five MDP elements is not used in episodic problems?

Answer 21

Gamma, it is useless in episodic problems like the supermarket problem.

Question 22

Which model or function is meant when we say “model-free” or “model-based”?

Answer 22

When we say “model-free” we refer to the absence of the environments model, such as the transition function.

Question 23

What type of action space and what type of environment are suited for value-based methods?

Answer 23

Discrete action space and discrete/continuous state space/environment.

Question 24

Why are value-based methods used for games and not for robotics?

Answer 24

Because robotics is in the real-world where we have continuous action spaces.

Question 25

Name two basic Gym environments.

Answer 25

The cartpole problem and the lunar lander