Module 8

Question 1

What is reinforcement learning

Answer 1

• based on rewarding desired behaviors / punishing undesired ones

Question 2

What is reinforcement agent capable of

Answer 2

• is able to perceive and interpret its env to take actions and learn through trial and error

Question 3

Where can reinforcement learning operate?

Answer 3

as long as a clear reward can be applied

Question 4

What is optimal policy

Answer 4

• yields highest expected utility

Question 5

What does a Markov decision process contain

Answer 5

• Possible world states S
• Set of Models
• Set of possible actions A
• reward function R(s,a)
• A policy the solution of MDP

Question 6

What is a state in MDP

Answer 6

• set of tokens that represent every state the agent can be in

Question 7

What is a model / transition model in MDP

Answer 7

• Gives an action’s effect in a state

Question 8

How is the transition model defined

Answer 8

• defined by T(S, a, S’)

- in state S, take action A, ends in State S’

Question 9

How does the modal differ in stochastic actions?

Answer 9

Add in probability P(S’| S,a) - probability of S’ given S and a

Question 10

What is they key feature of Markov Property

Answer 10

effects of an action taken in a state depend only on that state and not prior history

Question 11

What is an action in MDP

Answer 11

• set of all possible action

- A(s) defines the set of actions that can eb taken given state s

Question 12

What is a reward in MDP

Answer 12

• real values reward function
• R(s) indicates reward for being in state s
• R(s,a) indicates reward being in state s after taking action a
• R(S, a, S’) indicates reward for being in state S’ from S after action A

Question 13

What is policy in MDP

Answer 13

• solution to the MDP
• maps from S to a
• indicates action a to be taken while in state S

Question 14

What do MDP solutions usually involve?

Answer 14

dynamic programming

- recursively breaking a problem into pieces while remembering optimal solutions to each piece

Question 15

How is the quality measured of a policy

Answer 15

• measured through expected utility

- denoted by pi*

Question 16

What is the goal of MDP and what role does RL play

Answer 16

Goal - maximize cumulative reward in LT
RL - transitions and rewards usually not available
- how to change policy given experience
- how to explore environment

Question 17

Describe Episodic vs continuing tasks in MDP (optimality/horizon)?

Answer 17

Episodic

• finite horzion = game ends after N steps
• optimal policy depends on N - harder to analyze
• Policy depends on time = nonstationary

Continuing tasks

• infinite horizon = no time limit
• optimal action depends on current state and is stationary

Question 18

What are additive rewards

Answer 18

• infinite value for continuing tasks

Question 19

what are discontinued rewards

Answer 19

where y is 0 < 1 - discount factor describes preference if an agent for current rewards over future rewards

where y is close to 0 - rewards in distant future are insignificant

where y is close to 1 - agent is more willing to wait for long-term rewards

when y is exactly 1 - discounted rewards reduce to the special case of purely additive rewards

Question 20

What is the utility of the state

Answer 20

• expected reward for next transition + discounted utility of next stare assuming agent chooses optimal solution
• given by bellman equation

Question 21

What is the state value function

Answer 21

denoted - U pi (s)

- expected return when starting in s and following pi

Question 22

What is the state-action value function

Answer 22

denoted - Q pi (s, a) AKA Q funtion

- expected return when starting in s, performing a and following pi

Question 23

What are value functions useful for

Answer 23

useful for finding the optimal policy

• can est from experience
• pick the best action using Q function

Question 24

How does RL differ from MDP

Answer 24

• Don’t know transition model T or Reward R

- must try actions and states to learn

Question 25

What are the basic ideas of RL

Answer 25

Exploration - you have to try unknown actions to get info Exploitation - you have to use what you know Sampling - you may need to repeat many times to get good estimates Generalization - what you learn in one state may apply to others

Question 26

How do you receive feedback in RL, What is agents utility in RL

Answer 26

- receive feedback in form of rewards | - utility is reward function

Question 27

Offline vs Online

Answer 27

Offline is MDP online is RL

Question 28

What is the idea of model based learning

Answer 28

- the agent uses the transition model of the environment to make decisions - Assumes learned model is correct - learn an appx model based on experiences

Question 29

What is step 1 of MBL

Answer 29

Learn empircal MDP model - count outcomes s' for each s, a - normalize to give estimate of T(s,a,s') - Discover each reward when we experience (S, a, s')

Question 30

What is step 2 of MBL

Answer 30

- solve learned MDP

Question 31

Pros and Cons of MBL

Answer 31

Pro - makes efficient use of experiences Con - may not scale to large state spaces - learns model one state-action pair at a time

Question 32

What is the simplified task of passive reinforcement learning

Answer 32

``` Policy evaluation - Input - a fixed policy pi(s) - agent tries to learn the utility pi (s) - Don't know transition model and reward the goal is to learn state values ```

Question 33

Run through passive reinforcement learning

Answer 33

1. Agent executes set of trials in env using policy 2. Agent started in the initial state and reaches one of the terminal states 3. Agent percepts supply current state and reward for transition to reach that state

Question 34

What is the utility in Passive reinforcement learning

Answer 34

- is defined as expected sum of (discounted ) rewards obtained if policy followed

Question 35

What is the goal of direct evaluation

Answer 35

Compute values for each state under pi

Question 36

What is the idea of Direct Evaluation

Answer 36

Average observed sample values - Act according to pi - write down sum of discounted rewards when visiting state - average those samples

Question 37

What does direct evaluation do to RL

Answer 37

reduces it to standard supervised learning with state and reward pair

Question 38

Pros and cons of direct evaluation

Answer 38

Pros - Easy to understand - No knowledge of T, R required - eventually computes correct avg values using just sample transitions Cons - wastes information about state connections - each state learned separately - violates Bellman equations - slow

Question 39

Why not use policy evaluation

Answer 39

Still need T and R although it exploits the connection between states

Question 40

What is the idea of sample based policy evaluation

Answer 40

take samples of outcomes by doing the action and then average

Question 41

What is the idea of Temporal difference learning TDL

Answer 41

- update U each time we experience transition | - likely outcomes will contribute updates more often

Question 42

How does TDL learn

Answer 42

- Policy is still fixed , still evaluating | - Take the running average - move values toward successor value

Question 43

Problems of TD value learning and solution

Answer 43

- cannot turn values into new policy | - solution - learn Q values , make action selection model free

Question 44

Known MDP vs Unknown MDP

Answer 44

Known MDP - offline solution - policy evaluation Unkown MDP model based - fixed policy evaluated on appx MDP Unkown MDP model free - Evaluate fixed policy at value learning - Q learning - PRL - DE - TDL