Definition of Reinforcement Learning#

The direct neural network training process, always feeds the data to the model directly. The target is to improve its perceptibility (like CNN) instead of the decision-making capability. The Reinforcement Learning (RL) showed up to make the agent learn from the feedback from the enviroment. With the reward from the enviroment, the dicision made by the agent can gradually meet the human’s expectation. In machine learning area, with a trainable agent, we hope it can find the optimal strategies to the certain decision problem.

Formulaically, all the reinforcement learning can be seen as a MDP. The solution to such scenario, is also the solution of the RL.

Markov Process#

In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, “What happens next depends only on the state of affairs now.” A countably infinite sequence, in which the chain moves state at discrete time steps, gives a discrete-time Markov chain (DTMC). A continuous-time process is called a continuous-time Markov chain (CTMC). Markov processes are named in honor of the Russian mathematician Andrey Markov¹.

A Markov process is a stochastic process that satisfies the Markov property. It’s simply “memorylessness”. The predictions can be made regarding future outcomes based solely on its present state and—most importantly—such predictions are just as good as the ones that could be made knowing the process’s full history. Formally:

Markov Decision Process#

Formally, a MDP is a 4-tuple ($S,A,P_a, R_a$), where:

• $S$: the state space.
• $A$: the action space ($A_s$ is the set of available actions from state $s$)
• $P_a(s,s')$: the paobability that action $a$ in state $s$ at time $t$ will lead to state $s'$ at time $t+1$. Generally:$Pr(s_{t+1}\in S' | s_t = s, a_t=a) = \int _{S'} P_a(s,s')ds'$, for every $S'\sube S$.
• $R_a(s,s')$: immediate reward received after transitioning from state $s$ to state $s'$.

Usually, the optimization objective of MDP is to find a good policy for the decision maker. Thus, there exsists a policy function $\pi$, a (potentially probabilistic) mapping from $S$ to $A$. Combined with the MDP, the policy fixes the resulting combination behaves. The objective is to choose a policy $\pi$, maximizes some cumulative function of the random rewards:

where $\gamma$ is the discount factor satisfying $0\leq \gamma \leq \ 1$, which is usually close to 1 (for example, $\gamma =1/(1+r)$ for some discount rate $r$). A lower discount factor motivates the decision maker to favor taking actions early, rather than postpone them indefinitely².

The algorithms to calculate optimal policies for finite state and sction MDPs requires storage for two arrays indexed by state: value $V$ and policy $\pi$. At the end of the algorithm, $\pi$ will contain the solution and $V(s)$ will contain the discounted sum of the rewards to be earned by following that solution from state $s$.

To simplify the represatation, we introduce some new definition and notation to help understanding:

• $R(s)$: means the expectation of the reward gained at the next time stamp under state $s$, $R(s) = E_{a \in A_s} [R_a(s,s')]$.
• $G_t$: Return, the sum of the declined reward from a state $s_t$ in a Markov Chain. $G_t = \sum _ {i=0}^{\infty }\gamma ^i R(s_{t+1+i})$.

Usually, the state indexed value function $V(s)$ is called the state value fcuntion, it’s the expectation of the gain from the certain state $s$ in a Markov Chain, $V(s) = E[G_t|S_t = s]$