D-DL4CV-Lec21a-MDP

Introduction

Definition

MDP is like a mathematical blueprint that captures all the necessary information for the network to make decision. It can be express with a tuple $(S,A,R,P,\gamma )$

Explanation

$S$ : The Set of Possible States

States represent every situation that the agent might find itself in

$A$ : The Set of Possible Actions

Actions represent all the possible choices available for the agent

$R$ : The Reward Distribution

When the agent takes an action, the reward will be sampled from $R$

$P$ : The Transition Distribution

When we transit from $s_t$ to $s_{t+1}$ by $a_t$. $s_{t+1}$ is not fixed. Instead, it is sampled from $P$

$\gamma$ : The Discount Factor

How much should the future rewards matter compared to immediate ones in current decision making?

The discount factor encodes this tradeoff

Markov Property

The current state $s_t$ completely describe the current world. The agent only makes decision based on $s_t$ and has no need to take history into consideration

Process

Policy $\pi$ : The Action Probability Distribution

The agent samples an action $a_t$ from policy $\pi (a|s_t)$

Steps

• At time step $t=0$, environment samples initial state $s_0\sim p(s_0)$
• Then, repeat till done:
  • Agent selects an action $a_t\sim \pi (a|s_t)$
  • Environment samples reward $r_t\sim R(r|s_t,a_t)$
  • Environment samples next state $s_{t+1}\sim P(s|s_t,a_t)$
  • Agent receives reward $r_t$ and next state $s_{t+1}$