测试数学公式
chrome浏览器需要安装mathjax插件才能浏览正确的公式
策略 (Policy)是一个函数，输入当前的状态 s，输出采取动作 a 的概率 $\pi(s,a)$.
一个策略 $ \pi $ 下的一个状态s的价值v(s)定义：按照这个策略，从这个状态出发，系统能够获得的递减奖励期望:
\[v(s)= E_{\pi}[\sum_{k=0}^\infty \gamma^k R_{k} ]= E_{\pi}[R_{0}+\gamma R_{1}+...]\] \[v(s)= \sum_{a \in A}\pi(s,a)( R_{s,a}+\gamma\sum_{s' \in S}T_{s,a}^{s'}v(s') )\]将价值扩展到状态-动作对上。一个状态-动作对的价值定义如下所示。
\[q(s,a)=R(s,a)+ E_{\pi}[\sum_{k=1}^\infty \gamma^k R_{k} ]\]确定性(determinative)策略改进：对于一个状态s，让策略选择可以获得最大回报的一个动作a：
\[\pi_{i+1}(s,a) = \begin{cases} 1, & a = argmax_{a}R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v(s') \\[2ex] 0, & a \neq argmax_{a}R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v(s') \end{cases}\]模型无关 (Model-free) 的状态值估计
1. 蒙特卡罗(monte carlo)
在当前策略下，多次探索，每次探索产生如下采样序列：
\[s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},...,s_{k},a_{k},r_{k}\]在序列第一次碰到或者每次碰到一个状态s时，计算其衰减奖励(reward):
\[g_s= r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+...+\gamma^{t+l} r_{t+l}\]最后更新状态价值
\[\begin{align} S(s) = S(s) +g_{s}\\ N(s) = N(s)+1 \\ v(s) = \frac{S(s)}{N(s)} \end{align}\]2. 时差(Temperal Difference)
\[v(s) = v(s)+\gamma (r + \gamma (v(s')-v(s)))\] struct sar{
int state, int action;
double reward;
}
std::map<int,double>> value_by_TD(const vector<vector<sar>>& sar_samples,const double alpha,const double gamma){
std::map<int,double>> Values;
std::set<int> states;
double V_s1;
for(int i = 0 ; i<sar_samples.size();i++)
for(int j = 0 ; j<sar_samples[i].size();j++){
int s = sar_samples[i][j].state;
if (Values.find(s) == myMap.end())
Values.insert(std::make_pair(s,0.0));
}
for(int i = 0 ; i<sar_samples.size();i++)
for(int j = 0 ; j<sar_samples[i].size();j++){
int s = sar_samples[i][j].state;
double r = sar_samples[i][j].reward;
if(j+1<sar_samples[i].size()) {
int s1 = sar_samples[i][j].reward;
V_s1 = Values[s1];
}
else V_s1 = 0.0;
Values[s] += alpha * (r + gamma * V_s1 - Values[s]);
}
return Values;
}
std::map<int,double>> value_by_TD(const vector<vector<sar>>& sar_samples,const double alpha,const double gamma){
//略
}
Written on August 22, 2017