TD算法伪代码

‘壹’ 什么是伪代码

1.
伪码（Pseudocode）是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。
介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。
2.
使用伪代码，
不用拘泥于具体实现。相比程序语言（例如Java,
C++,C,
Dephi
等等）它更类似自然语言。它是半角式化、不标准的语言。可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。
3.
人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意：这里是实现，不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个（用其他编程语言编写的程序的）功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。伪代码是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。

‘贰’ 伪码是什么

伪代码是一种算法描述语言。 使用伪代码的目的是使所描述的算法能够在任何编程语言（Pascal、C、Java 等）中轻松实现。 因此，伪代码必须结构清晰，代码简单，可读性强，类似于自然语言。 介于自然语言和编程语言之间。

以编程语言的书面形式指定算法的功能。 使用伪代码，不要拘泥于具体的实现。 与编程语言（如Java、C、C、Dephi等）相比，它更类似于自然语言。

它是一种半宽的非标准语言。 整个算法运算过程的结构可以用接近自然语言的形式来描述（任何你熟悉的文字都可以，关键是要表达程序的意思）。

防伪码的特色：

标识的仅有性。任何一枚防伪码标识都是仅有的;且只能一次性全程运用，冒充者无法仿造重复运用。

辨别的简易性。消费者不管在何时何地均可经过程控电话输入标识上的编码，由计算机体系主动辨别，即可得到生产厂家、商品真伪等有关信息，全过程只需几十秒。

办理的统一性。此防伪标识物可用于任何种类的商品上，利用遍布全国的电话网络，建立起全国性的打假防伪网络，随时(监)控、统一办理。

功用的延展性。防伪码除了具有商品防伪和为入网公司供给有关效劳外，还可在打击、票证办理、网上营销等方面表现其共同和活跃的作用，能够大幅度下降人工打假的费用。

‘叁’ C语言中的“伪码”到底是啥

就是伪代码，也就是就是用常规语言或文字符号（即非编程语言写的）代码算法，叫伪代码

只是为了直观的表达出算法，才用伪代码，还有相应的伪代码语言等，这些代码无法运行，只有通过按照伪代码所表达的算法或操作，编好程序，才能运行. 举例，我要表达c语言中的i++操作，我可以些成"i自加1"，当然一看就知道i自加1是机器读不懂的这种用人能看懂，机器看不懂的语言来描述程序逻辑和结构的代码就是伪代码了……

‘肆’ 伪代码与源代码如何区分

伪代码：只是一种描述算法结构的语言，只是用来说明一些问题，伪代码并不能执行。如大学课程《数据结构》。比如要描述一个流程，你可以这么写伪代码：
if
登陆成功
then
跳转页面
else
出错
这一段看像是程序，实际上只有人能看懂，真正要编程语言来实现上面的功能，你就不能那么写。
源代码：是用汇编、C、C++等编写好但还没编译成机器可执行的代码。

‘伍’ 蒙特卡洛，时序差分Temporal-Difference Learning(TD)算法

1.蒙特卡洛
Monte-Carlo算法：
1.将agent放入环境的任意状态
2.从这个状态开始选择action, 并进入下一个状态
3.重复第二步直到达到最终状态
4.从最终状态回溯，计算每一个状态的G值
5.重复1-4过程，然后平均每一次的G值，最后得到的就是V值

关于G值：
第一步：根据策略使agent做出动作并进入下一动作，直到到达最终状态，需要记录每一个状态的转移，得到奖励r
第二步：从最终状态回溯，一遍一遍计算G值。 G 等于上一状态的G值（G‘）乘以一定的折扣（gamma）再加上r

G值就是从某个状态到最终状态的奖励总和

G就是V的更新目标，关于MC的更新：
两种方法：

2.时序差分(TD)算法
TD是对MC的改进，即agent走到第N步就可以开始回溯更新。

‘陆’ 计算机算法的伪代码是什么

算法中的伪代码是指采用类似于C语言或Pascal语言或ada语言来描述算法。之所以说类似，是因为描述算法的语言与真正的（或实际使用的）C语言或Pascal或ada语言有些差异。不过这些差异不大。
或者从另一个角度讲，算法中的伪代码与编译器无关。

‘柒’ 强化学习基础篇（十八）TD与MC方法的对立统一

前面介绍TD的过程中，我们已经提到过一些TD和MC的区别，例如在Bias与Variance角度看：

a. MC具有高方差，为无偏估计

b. TD具有低方差，为有偏估计

a. TD可以在知道最终结果之前就进行学习。

b. TD也可以在没有最终输出的场景下进行学习。

假设只有有限的经验，比如10幕数据或100个时间步。在这种情况下，使用增量学习方法的一般方式是反复地呈现这些经验，直到方法最后收敛到一个答案为止。给定近似价值函数 ，在访问非终止状态的每个时刻 ，使用下面两式计算相应的增量但是价值函数仅根据所有增量的和改变一次。

然后，利用新的值函数再次处理所有可用的经验，产生新的总增量，依此类推，直到价值函数收敛。我们称这种方法为批量更新，因为只有在处理了整批的训练数据后才进行更新。

在批量更新下，如果经验趋于无穷多，只要选择足够小的步长参数 ， 就能确定地收敛到与 无关的唯一结果。常数 MC方法在相同条件下也能确定地收敛，但是会收敛到不同的结果。

当然，这是在经验趋于无穷（也即无数次试验）的情况下达到的理想情况，但是实际中我们不可能达到，那如果我们利用有限的经验来对值函数进行估计将得到什么样的结果？比方说，对于下面这 个 episode：

如果我们重复从这 个episode中进行采样，对于某一次采样得到的样本 应用MC或者 方法，会得到什么样的结论呢？先来看一个例子。

假设在一个强化学习问题中有A和B两个状态，模型未知，不涉及策略和行为，只涉及状态转换和即时奖励，衰减系数为1。现有如下表所示8个完整状态序列的经历，其中除了第1个状态序列发生了状态转移外，其余7个完整的状态序列均只有一个状态构成。现要求根据现有信息计算状态A、 B的价值分别是多少？

考虑分别使用MC算法和TD算法来计算状态A、 B的价值：

对于MC算法：

在8个完整的状态序列中，只有第一个序列中包含状态A，因此A价值仅能通过第一个序列来计算：

所以可以得到 。

状态B的价值，则需要通过状态B在8个序列中的收获值来平均：

可以得到 。

对于TD算法 ，

再来考虑应用TD算法。TD算法试图利用现有的episode经验构建一个MDP（如下图），由于存在一个episode使得状态A有后继状态B，因此状态A的价值是通过状态B的价值来计算的，同时经验表明A到B的转移概率是100%，且A状态的即时奖励是0，并且没有衰减，因此A的状态价值等于B的状态价值。

其计算过程如下：

因此在TD算法下 。

AB Example体现了通过批量 和批量蒙特卡洛方法计算得到的估计值之间的差别。批量蒙特卡洛方法总是找出最小化训练集上均方误差的估计，而批量 总是找出完全符合马尔科夫过程模型的最大似然估计参数。一个参数的最大似然估计是使得生成训练数据的概率最大的参数值。

TD与MC的另一个差异

现在为止所阐述的MC学习算法、TD学习算法和DP算法都可以用来计算状态价值。它们的特点也是十分鲜明的，MC和TD是两种在不依赖模型的情况下的常用方法，这其中又以MC学习需要完整的状态序列来更新状态价值，TD学习则不需要完整的状态序列；DP算法则是基于模型的计算状态价值的方法，它通过计算一个状态 所有可能的转移状态 及其转移概率以及对应的即时奖励来计算这个状态 的价值。

下图，非常直观的体现了三种算法的区别。

综合上述三种学习方法的特点，可以小结如下：

当使用单个采样，同时不经历完整的状态序列更新价值的算法是TD学习； 当使用单个采样，但依赖完整状态序列的算法是MC学习； 当考虑全宽度采样，但对每一个采样经历只考虑后续一个状态时的算法是DP学习； 如果既考虑所有状态转移的可能性，同时又依赖完整状态序列的，那么这种算法是穷举（exhausive search）法。

需要说明的是：DP利用的是整个MDP问题的模型，也就是状态转移概率，虽然它并不实际利用采样经历，但它利用了整个模型的规律，因此也被认为是全宽度（full width） 采样的。

‘捌’ 写出算法的伪代码

伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

下面介绍一种类Pascal语言的伪代码的语法规则。

伪代码的语法规则
在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）；
书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进；
例如：

line 1
line 2
sub line 1
sub line 2
sub sub line 1
sub sub line 2
sub line 3
line 3
而在Pascal中这种关系用begin和end的嵌套来表示，

line 1
line 2
begin
sub line 1
sub line 2
begin
sub sub line 1
sub sub line 2
end;
sub line 3
end;
line 3在C中这种关系用{ 和 } 的嵌套来表示，

line 1
line 2
{
sub line 1
sub line 2
{
sub sub line 1
sub sub line 2
}
sub line 3
}
line 3
在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时也可省略标号。
例如：

1. line 1
2. line 2
a. sub line 1
b. sub line 2
1. sub sub line 1
2. sub sub line 2
c. sub line 3
3. line 3符号△后的内容表示注释；
在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与C或C++不同；
在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就使用全局变量；
赋值语句用符号←表示，x←exp表示将exp的值赋给x，其中x是一个变量，exp是一个与x同类型的变量或表达式（该表达式的结果与x同类型）；多重赋值i←j←e是将表达式e的值赋给变量i和j，这种表示与j←e和i←e等价。
例如：

x←y
x←20*(y+1)
x←y←30
以上语句用Pascal分别表示为：

x := y;
x := 20*(y+1);
x := 30; y := 30;
以上语句用C分别表示为：

x = y;
x = 20*(y+1);
x = y = 30;
选择语句用if-then-else来表示，并且这种if-then-else可以嵌套，与Pascal中的if-then-else没有什么区别。
例如:

if (Condition1)
then [ Block 1 ]
else if (Condition2)
then [ Block 2 ]
else [ Block 3 ]
循环语句有三种：while循环、repeat-until循环和for循环，其语法均与Pascal类似，只是用缩进代替begin - end；
例如：

1. x ← 0
2. y ← 0
3. z ← 0
4. while x < N
1. do x ← x + 1
2. y ← x + y
3. for t ← 0 to 10
1. do z ← ( z + x * y ) / 100
2. repeat
1. y ← y + 1
2. z ← z - y
3. until z < 0
4. z ← x * y
5. y ← y / 2
上述语句用Pascal来描述是：

x := 0;
y := 0;
z := 0;
while x < N do
begin
x := x + 1;
y := x + y;
for t := 0 to 10 do
begin
z := ( z + x * y ) / 100;
repeat
y := y + 1;
z := z - y;
until z < 0;
end;
z := x * y;
end;
y := y / 2;
上述语句用C或C++来描述是：

x = y = z = 0;
while( z < N )
{
x ++;
y += x;
for( t = 0; t < 10; t++ )
{
z = ( z + x * y ) / 100;
do {
y ++;
z -= y;
} while( z >= 0 );
}
z = x * y;
}
y /= 2;
数组元素的存取有数组名后跟“[下标]”表示。例如A[j]指示数组A的第j个元素。符号“ …”用来指示数组中值的范围。
例如：

A[1…j]表示含元素A[1], A[2], … , A[j]的子数组；

复合数据用对象(Object)来表示，对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。
例如：

数组可被看作是一个对象，其属性有length，表示其中元素的个数，则length[A]就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号，一般来说从上下文可以看出其含义。

用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值y←x就使f[y]=f[x]，更进一步，若有f[x]←3，则不仅有f[x]=3，同时有f[y]=3，换言之，在赋值y←x后，x和y指向同一个对象。

有时，一个指针不指向任何对象，这时我们赋给他nil。

函数和过程语法与Pascal类似。
函数值利用 “return (函数返回值)” 语句来返回，调用方法与Pascal类似；过程用 “call 过程名”语句来调用；

例如：

1. x ← t + 10
2. y ← sin(x)
3. call CalValue(x,y)
参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。

‘玖’ 什么是Temporal Difference (TD)

Temporal difference 是通过没有环境先验知识的一组episode从环境中学习的一个代理。
这意味着时间差异采用无模型或无监督学习方法。也就是从过去经验中学习。

Gamma (γ): 折扣率，一个介于 0 和 1 之间的值。值越高，您打折的就越少。
Lambda (λ): 信用分配变量。一个介于 0 和 1 之间的值。值越高，您可以分配给更远的状态和操作的功劳越大。
Alpha (α): 学习率。我们应该接受多少错误并因此调整我们的估计。一个介于 0 和 1 之间的值。较高的值会积极调整，接受更多的误差，而较小的值会保守调整，但可能会更保守地向实际值移动。
Delta (δ): 价值的变化或差异。

所以我们着手的第一个算法是 TD(1)。 TD(1) 以与 Monte Carlo 相同的方式在回合结束时更新我们的值。所以回到我们的随机游走，随机向左或向右走，直到降落在“A”或“G”。一旦回合结束，则对先前状态进行更新。正如我们上面提到的，如果 lambda 值越高，信用可以分配得越远，在这种情况下，它是 lambda 等于 1 的极端。这是一个重要的区别，因为 TD(1) 和 MC 仅适用于回合环境，这意味着它们需要一个'finish line' 进行更新。

现在让我们看看算法并尝试理解这一点。 Gt（图 2）是我们剧集中所有奖励的折扣总和。因此，当我们在我们的环境中穿越时，我们会跟踪所有奖励并将他们折扣求和。所以让我们表现得好像我们在大声朗读：给定点（时间，t+1）的即时奖励（R）加上未来奖励（Rt+2）乘以折扣（γ）等等。未来的折扣更多(γ^T-1)，越是远，折扣的越多。。因此，如果 γ=0.2 并且您在时间步骤 6 对奖励进行折扣，则您的折扣值 γ 变为 γ^6–1，等于 0.00032。仅在 6 个时间步长后就明显变小了。