---
# System prepended metadata

title: introduction to reinforcement learning
tags: [rl]

---

---
title: introduction to reinforcement learning
tags: rl
---

# introduction to reinforcement learning!

#### how is reinforcement learning different from other machine learning paradigms?

- there is no supervisor, only a *reward* signal
- feedback is delayed, not instantaneous
- time really matters (sequential, non i.i.d data)
- agent's actions affect the subsequent data it receives

### rewards
- a reward $R_t$ is a scalar feedback signal
- indicates how well agent is doing at step t
- the agent's job is to maximize cumulative reward

reinforcement learning is based on the reward hypothesis
#### reward hypothesis definition
all goals can be described by the maximization of expected sumulative reward

#### sequential decision making
- goal: select actions to maximize total future reward
- actions may have long term consequences
- reward may be delayed
- it may be better to sacrifice immediate reward to gain more long-term reward

### environment
![](https://i.imgur.com/K7jtlYw.png)

at each step t, the agent:
- executes action $A_t$
- receives observcation $O_t$
- receives scalar reward $R_t$

the environment:
- receives action $A_t$
- emits observation $O_{t+1}$
- emits scalar reward $R_{t + 1}$

t increments at environment step

### state

#### history and state
the history is the sequence of observations, actions, rewards

$H_t$ = $O_1$, $R_1$, $A_1$, ..., $A_{t - 1}$, $O_t$, $R_t$

i.e all observable variables up to time t
i.e the sensorimotor stream of a robot or embodied agent

what happens next depends on the history
- the agent selects actions
- the environment selects observations/rewards

 **state** is the information used to determine what happens next

formally, state is a function of the history

$S_t$ = f($H_t$)

#### environment state

the **environemt state** $S^e_t$ is the environment's private representation

i.e. whatever data the environment uses to pick the next observation/reward

- the environment state is not usually visible to the agent
- even if $S^e_t$ is visible, it may contain irrelevant information


#### agent state
the **agent state** $S^a_t$ is the agent's internal representation

i.e. whatever information the agent uses to pick the next action

i.e. it is the informtion used by reinforcement learning algorithms

- it can be any function of history:
$S^a_t$ = f($H_t$)

#### information state
an **information state** (**Markov state**) contains all useful information from the history

a state $S_t$ is **Markov** if and only if

$\mathbb{P}$[$S_{t + 1}$ | $S_t$] = $\mathbb{P}$[$S_{t + 1}$ | $S_1$,...,$S_t$]

- the future is independent of the past given the present

$H_{1:t}$ -> $S_t$ -> $H_{t + 1: \infty}$

- once the state is known, the history may be thrown away
- i.e. the state is a sufficient statistic of the future
- the environment state $S^e_t$ is Markov
- the history $H_t$ is Markov

#### fully observable environments

**full observability**: agent **directly** observes environment state

$O_t$ = $S^a_t$ = $S^e_t$

- agent state = environment state = information state
- formally, this is a **Markov decision process** (MDP)

#### partially observable environments

**partial observability**: agent **indirectly** observes environment:
- a robot with camera vision isn't told its absolute location
- a trading agent only observes current prices
- a poker playing agent only observes public cards

now agent state ≠ environment state

- formally this is a **partially observable Markov decision process**

agent must construct its own state representation $S^a_t$, e.g.
- complete history: $S^a_t$ = $H_t$
- beliefs of environment state: $S^a_t$ = ($\mathbb{P}$[$S^e_t$ = s^1^], ..., $\mathbb{P}$[$S^e_t$ = s^n^])
- recurrent neural network: $S^a_t$ = $\sigma$($S^a_{a - 1}$$W_s$ + $O_t$$W_o$)

### major components of an RL agent

an RL agent may include one or more of these components
- policy: agent's behavior function
- value function: how good is each state and/or action
- model: agent's representation of the environment


#### policy

a policy is the agent's behavior, a map from state to action

deterministic policy: a = $\pi$(s)
stochastic policy: $\pi$(a | s) = $\mathbb{P}$[$A_t$ = a | $S_t$ = s]

#### value function

a value function is a prediction of future reward used to evaluate the goodness/badness of states and therefore to select between actions e.g.

$v_\pi$(s) = $\mathbb{E}_\pi$[$R_{t+1}$ + $\gamma R_{t+2}$ + $\gamma ^2R_{t+3}$ + ... | $S_t$ = s]

#### model 

a model predicts what the environment will do next
 
P predicts the next state, R predicts the next (immediate) reward, e.g.

$P^a_{ss'}$ = $\mathbb{P}$[$S_{t+1}$ = s' | $S_t$ = s, $A_t$ = a]

$R^a_{s}$ = $\mathbb{E}$[$R_{t+1}$ | $S_t$ = s, $A_t$ = a]

### categorizing RL agents

value based
- no policy (implicit)
- value function

policy based
- policy
- no value function

actor critic
- policy
- value function

model free
- policy and/or value function
- no model

model based
- policy and/or value function
- model

### problems within RL

two fundamental problems in sequential decision making
- reinformcent learning
    - the environment is initally unknown
    - the agent interacts with the environment
    - the agent improves the policy
- planning
    - a model of the environment is known
    - the agent performs computations with its model (without any external interaction)
    - the agent improves its policy
    - aka deliberation, reaosning, introspection, pondering, thought, search


exploration and exploitation
- reinforcement leanring is like trial-and-error learning
- the agent should discover a good policy from its experiences of the environment without losing too much reward along the way
- exploration finds more information about the environment
- exploitation exploits known information to maximize reward
- it is isually important to explore as well as exploit


prediction and control
- prediction: evaluate the future (given a policy)
- control: optimize the future (find the best policy)

