<commit_before>---
layout:       post
title:        "马尔可夫决策过程MDP"
subtitle:     "MDP"
date:         2018-05-31 10:12:00
author:       "xuepro"
header-img:   "img/home_bg.jpg"
header-mask:  0.3
catalog:      true
multilingual: true
tags:
    - AI
    
---

**A stochastic process** is an indexed collection of random variables $$ {X_t} $$.
 e.g., time series of weekly demands for a product
 
**A stochastic process $$ X_t $$** is said to be Markovian if and only if

$$ P(X_{t+1}=j| X_t=i,X_{t-1}=k_{t-1},X_{t-2}=k_{t-2},...X_1=k_1,X_0=k_0) = P(X_{t+1}=j|X_0=k_0) $$

   “The future is independent of the past given the present”
   
**A Markov process** (or **Markov chain**) is a **memoryless** stochastic process, i.e., a sequence of random states
$$s_1; s_2; : : :$$ with the Markov property

**A Markov process**  is a is a tuple $$(S;P;\mu)$$

- S is a (finite) set of states
- P is a state transition probability matrix, $$ P_{ss'} = P(s'\vert s) $$
 
- a set of initial probabilities $$ \mu_j^0 = P(X_0=i)$$ for all i

**A Markov reward process** is a Markov process with values.
A Markov Reward Process is a tuple $$S;P;R;\gamma; \mu $$

- S is a (finite) set of states
- P is a state transition probability matrix, $$P_{ss'} = P(s'\vert s) $$

- **R** is a reward function, $$R_s = E[r \vert s]$$
- **$$\gamma$$** is a discount factor,  $$\gamma \in[0,0]$$
- a set of initial probabilities $$ \mu_j^0 = P(X_0=i)$$ for all i

The **return** $$v_t$$ is the total discounted reward from time–step t.
  $$v_t = r_{t+1}+\gamma r_{t+2}+\gamma r^2 r_{t+3}+--- = \sum_{k=0}^{\infty}\gamma ^k r_{t+k+1} $$
  
The **state value function** V(s) of an MRP is the expected return starting from state s
        $$ V(s) = E[v_{t}\vert s_{t}=s]$$
        
### Bellman Equation 

$$\begin{equation}\begin{split}
   V(s) = E[v_{t}\vert s_{t}=s] \\
        = E[r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+ ...\vert s_{t}=s]\\      
        = E[r_{t+1}+\gamma (r_{t+2}+\gamma r_{t+3}+ ...) \vert s_{t}=s]\\
        = E[r_{t+1}+\gamma v_{t+1}\vert s_{t}=s]\\
        = E[r_{t+1}+\gamma V(s_{t+1})\vert s_{t}=s]
\end{split}\end{equation}
$$

So, We get the  Bellman Equation:

$$\begin{equation}\begin{split}
  V(s) = E[r+ \gamma V(s')\vert s]=  R_{s}+\gamma sum_{s'\in S} P_{ss'}V(s')$$
\end{split}\end{equation}
$$

数学符号 refer:

数学符号的竖线|有时需要用```\vert```表示
[List of Greek letters and math symbols](https://www.sharelatex.com/learn/List_of_Greek_letters_and_math_symbols)

[2](http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html)<commit_msg>Update 2018-05-31-马尔可夫决策过程MDP.md<commit_after>---
layout:       post
title:        "马尔可夫决策过程MDP"
subtitle:     "MDP"
date:         2018-05-31 10:12:00
author:       "xuepro"
header-img:   "img/home_bg.jpg"
header-mask:  0.3
catalog:      true
multilingual: true
tags:
    - AI
    
---

**A stochastic process** is an indexed collection of random variables $$ {X_t} $$.
 e.g., time series of weekly demands for a product
 
**A stochastic process $$ X_t $$** is said to be Markovian if and only if

$$ P(X_{t+1}=j| X_t=i,X_{t-1}=k_{t-1},X_{t-2}=k_{t-2},...X_1=k_1,X_0=k_0) = P(X_{t+1}=j|X_0=k_0) $$

   “The future is independent of the past given the present”
   
**A Markov process** (or **Markov chain**) is a **memoryless** stochastic process, i.e., a sequence of random states
$$s_1; s_2; : : :$$ with the Markov property

**A Markov process**  is a is a tuple $$(S;P;\mu)$$

- S is a (finite) set of states
- P is a state transition probability matrix, $$ P_{ss'} = P(s'\vert s) $$
 
- a set of initial probabilities $$ \mu_j^0 = P(X_0=i)$$ for all i

**A Markov reward process** is a Markov process with values.
A Markov Reward Process is a tuple $$S;P;R;\gamma; \mu $$

- S is a (finite) set of states
- P is a state transition probability matrix, $$P_{ss'} = P(s'\vert s) $$

- **R** is a reward function, $$R_s = E[r \vert s]$$
- **$$\gamma$$** is a discount factor,  $$\gamma \in[0,0]$$
- a set of initial probabilities $$ \mu_j^0 = P(X_0=i)$$ for all i

The **return** $$v_t$$ is the total discounted reward from time–step t.
  $$v_t = r_{t+1}+\gamma r_{t+2}+\gamma r^2 r_{t+3}+--- = \sum_{k=0}^{\infty}\gamma ^k r_{t+k+1} $$
  
The **state value function** V(s) of an MRP is the expected return starting from state s
        $$ V(s) = E[v_{t}\vert s_{t}=s]$$
        
### Bellman Equation 

$$\begin{equation}\begin{split}
   V(s) = E[v_{t}\vert s_{t}=s] \\
        = E[r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+ ...\vert s_{t}=s]\\      
        = E[r_{t+1}+\gamma (r_{t+2}+\gamma r_{t+3}+ ...) \vert s_{t}=s]\\
        = E[r_{t+1}+\gamma v_{t+1}\vert s_{t}=s]\\
        = E[r_{t+1}+\gamma V(s_{t+1})\vert s_{t}=s]
\end{split}\end{equation}
$$

So, We get the  Bellman Equation:

$$\begin{equation}\begin{split}
  V(s) = E[r+ \gamma V(s')\vert s]=  R_{s}+\gamma sum_{s'\in S} P_{ss'}V(s')
\end{split}\end{equation}
$$

数学符号 refer:

数学符号的竖线|有时需要用```\vert```表示
[List of Greek letters and math symbols](https://www.sharelatex.com/learn/List_of_Greek_letters_and_math_symbols)

[2](http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html)
{'fraction_non_alphanumeric': 0.20643378725083877, 'fraction_numerical': 0.02289323070850602, 'mean_word_length': 3.346483704974271, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1880694', 'n_tokens_mistral': 2148, 'n_tokens_neox': 2054, 'n_words': 556}