Page cover image

#16: Reinforcement Learning

  • 3 min

#16: Reinforcement Learning content

Created
Topics

Characteristics

  • No supervisor, only reward signal
  • Feedback is delayed, not instantaneous
  • Time matters (sequential), non IID data
  • Actions affect the subsequent data

Composition

Reward

  • Scalar feedback signal
  • Received after each step

Reward Hypothesis of RL

Maximization of expected cumulative reward = goals of the task

History

Ht=O1,R1,A1,…,At−1,Ot,RtH_{t}=O_{1}, R_{1}, A_{1}, \ldots, A_{t-1}, O_{t}, R_{t}
  • Sequence of all observations, actions, rewards
  • Except the current action

State

St=f(Ht)S_t=f(H_t)
  • A function of history
  • Compresses the huge history sequence to a single vector

Environment State SteS_t^e

Env's private state (not visible to agent)
From which generates next observation & reward

Agent State Sta=fa(Ht)S_t^a=f^a(H_t)

Agent's internal representation
Any function of history
Inputs to the RL algorithm

Information State (Markov State)

Contains all useful info about the history
💡
Markov Property
The future is independent of the past given the present
P[St+1∣St]=P[St+1∣S1,…,St]\mathbb{P}\left[S_{t+1} \mid S_{t}\right]=\mathbb{P}\left[S_{t+1} \mid S_{1}, \ldots, S_{t}\right]
Question: 2 stage modeling?
  • StS_t relates to St−1S_{t-1}
  • But StS_t comes from St−1S_{t-1}
  • StS_t does not relate to St−2S_{t-2}

Environment

Fully Observable Environment

Ot=Sta=SteO_t=S_t^a=S_t^e
  • Agent directly observes env state
    ⇒ Markov Decision Process (MDP)

Partial Observable Environment

  • Agent indirectly observes env state
    ⇒ Partially Observable Markov Decision Process (POMDP)
    • e.g. CV, trading bot, poker bot
  • Agent must construct own state representation StaS_t^a
    E.g.
     Complete history: Sta=Ht Beliefs of environment state: Sta=(P[Ste=s1],…,P[Ste=sn]) Recurrent neural network: Sta=σ(St−1aWs+OtWo)\begin{aligned}&\text { Complete history: } S_{t}^{a}=H_{t} \\&\text { Beliefs of environment state: } S_{t}^{a}=\left(\mathbb{P}\left[S_{t}^{e}=s^{1}\right], \ldots, \mathbb{P}\left[S_{t}^{e}=s^{n}\right]\right) \\&\text { Recurrent neural network: } S_{t}^{a}=\sigma\left(S_{t-1}^{a} W_{s}+O_{t} W_{o}\right)\end{aligned}

Agent

notion image

Policy π\pi

Defines the agent's behavior: maps state to action
  • Deterministic policy: at=π(st)a_t=\pi(s_t)
  • Stochastic policy: π(a∣s)=P[At=a∣St=s]\pi(a \mid s)=\mathbb{P}\left[A_{t}=a \mid S_{t}=s\right]

Value Function vπ(s)v_{\pi}(s)

Predicts future reward by state
Evaluates goodness of states to choose an action
vπ(s)=Eπ[Rt+1+γRt+2+γ2Rt+3+…∣St=s]v_{\pi}(s)=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid S_{t}=s\right]

Model

Predicts immediate future state & reward by action
  • Next State: Pss′a=P[St+1=s′∣St=s,At=a]\mathcal{P}_{s s^{\prime}}^{a}=\mathbb{P}\left[S_{t+1}=s^{\prime} \mid S_{t}=s, A_{t}=a\right]
  • Next Action: Rsa=E[Rt+1∣St=s,At=a]\mathcal{R}_{s}^{a}=\mathbb{E}\left[R_{t+1} \mid S_{t}=s, A_{t}=a\right]

Algorithm

Reinforcement Learning

Rules are unknown
Learn directly from interactive game play
Perform actions, see scores, make plans

Exploitation & Exploration

Exploitation: perform the best know action
Exploration: do something random

Current Progress

Value function is hard to learn
use DL to model the value function

Question

  1. Is RL a MPS or an alternative method?
  1. Can combine supervised learning & RL?

Resources

Jan 2, 2022