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 個時間步長後就明顯變小了。