017 制定複雜決策

Post date: 2013/3/13 下午 12:57:05

本章中我們考察假設明天我們可能再次決策下,用於決策今天做什麼的方法。

循序決策問題(sequential decision problem)

賽局理論

循序決策問題

假設一個代理人處在圖 17.1(a)中所示的 4 * 3 的環境中。從初始狀態開始,他在每個時間步必須選擇一個行動。

在代理人到達一個標有 +1 或者 -1 的目標狀態時與環境的交互終止。

目前我們假設環境是完全可觀察的,因而代理人總是知道自己所在的位置。

圖17.1 (a) 一個簡單的 4*3 的環境,其呈現出面臨循序決策問題的代理人。(b)此環境的轉移模型示意:

「預期的」結果出現的機率為 0.8 ,但有 0.2 的機率代理人會垂直於預設方向地移動。撞牆的結果是沒有

移動。兩個終止狀態分別有 +1 和 -1 的回報,而其他所有狀態都有 - 0.04 的回報

轉移模型(transition model)

馬可夫式

動態貝氏網路

環境歷史

回報(reward)

馬可夫決策程序(Markov decision process 或 MDP)

最佳策略(optimal policy)

效用延長

圖17.1的MDP例子中,代理人效能是透過對存取過的狀態的回報求和來度量。此性能度量的選擇並非隨意,但對於

環境歷史中的效用函數並不是唯一的可能性,其表示為 Uh ([s0,s1,...,sn])。

多屬性效用理論

有限期或無限期

非穩態(nonstationary)

穩態(stationary)

穩態性是個看來無害的假設而且有一些很強的邏輯推論:在穩態性假設下有兩種給序號賦效用值的途徑:

1. 累加回報(addictive reward):

狀態序列的效用為

Uh([s0,s1,s2,...]) = R(s0) + R(s1) + R(s2) + ...

圖 17.1 中的 4*3 世界使用的就是累加回報。注意在我們用於啟發式搜尋演算法(第 3 章)的路徑

成本函數中,隱含地使用了累加性。

2. 折扣回報(discounted reward):

狀態序列的效用為

Uh([s0,s1,s2...]) = R(s0) + yR(s1) + y^2R(s2) + ...

其中折扣因數是一個介於0和1之間的數。折扣因數描述了代理人對於當前回報與未來回報相

比的偏好。當y接近於0時,遙遠未來的回報被認為無關緊要。而當 y 是1時,折扣回報就和

累加回報完全等價,所以累加回報是折扣回報的一種特例。對於動物和人隨時間變化的偏好而

言,折扣看來是個好的模型。折扣因數和利率( 1/y) -1 是等價的。

適當策略(proper policy)

平均回報

最佳策略與狀態的效用

包含序列之間折扣回報的總和決定給出狀態序列的效用,當在執行時我們可以藉由比較包含的

期望效用來比較策略。

價值疊代

價值疊代(value iteration)

效用的貝爾曼方程

17.1.2節定義效用為從它向前的折扣回報之期望總和。從這裡,這個狀態的效用值和它的鄰接

狀態的效用值有直接的關係:一個狀態的效用值是在該狀態得到的立即回報加上在下一個狀態的期望

折扣效用值,假定代理人選擇了最佳行動。

貝爾曼方程(Bellman equation)

價值疊代演算法

貝爾曼方程式用於求解 MDP 的價值疊代演算法的基礎。如果有 n 個可能的狀態,那麼就有 n

個貝爾曼方程,每個狀態一個方程。

貝爾曼更新(bellman update)

價值疊代的收斂

前面我們提到價值疊代最終會收斂在貝爾曼方程組的唯一解上。

收縮(contraction)

收縮函數的兩個重要屬性:

● 一個收縮函數只有一個不動點;如果有兩個不動點,對他們應用這個函數就部會得到更近的值了,因而不是收縮。

● 當把函數應用於任意參數時,值一定更接近於不動點(因為不動點不會移動),於是反覆使用的收縮函數總是以不動點為極限。

最大值範數(max norm)

策略損失

策略疊代

前一節中,我們發現即使在效用函數估計得不是很準確的情況下也可能得到最佳策略。如果

一個行動比其他行動明顯要好,那麼所涉及狀態的效用準確值不需要太精確。這見解暗示著

另一種找到最佳策略的方法。策略疊代(policy iteration)演算法從某個初始策略 拍0 開始,

交替執行下面兩個步驟:

● 策略評價(policy evaluation):

給定一個策略 拍i ,計算Ui = U^拍i,假設 拍i 被執行則每個狀態的效用。

● 策略改進(policy improvement):

透過基於Ui的向前看一步的方法[如同在公式(17.4)中],計算新的MEU策略 拍+1。

修正策略疊代(modified policy iteration)。

非同步策略疊代(asynchronous policy iteration)。

部分可觀察的馬可夫決策過程

完全可觀察

部分可觀察

部分可觀察MDP(Partially Observable MDP,或者簡寫成 POMDP)

部分可觀察的馬可夫決策過程之定義

為了能處理POMDP,我們必須先適當地定義他們。

感測模型P(e | s)

濾波

對於 POMDP 價值疊代

17.2 節描述個價值疊代演算法,其計算個狀態的效用價值。由於許多信念狀態是無限地,我們需要更多的創造性。

策略恰好相等於條件計畫

1. 令執行固定條件計畫P 的效用開始於實體狀態 s 為 ap(s)。

2. 在任何給定信念狀態 b ,最佳策略將選擇最高期望效用的條件計畫執行,並且在最佳效用下 b 的期望效用正好是條件計畫的效用:

U ( b ) = U拍^*(b) = maxp b * ap

優勢

POMDP 的線上代理人

本節中,我們概要介紹一種部分可觀察的隨機環境中的代理人的全面設計方法。

● 用動態貝氏網路 (如第15章中所描述的) 表示的轉移和觀察模型。

● 如同用於第 16 章中的決策網路一樣,用決策和效用節點擴展動態貝氏網路。產生的模型被稱為

動態決策網路(dynamic decision network)或者簡寫為DDN。

● 使用濾波演算法把每個新的感知資訊與行動結合起來,並對信念狀態表示進行更新。

● 透過向前投影可能的行動序列並選擇其中的最佳行動,來制定決策。

因式表現法

基於效用的代理人

多代理人的決策:賽局理論

賽局理論

完全資訊

不完全資訊

1. 代理人設計:

賽局理論可以分析代理人的決策,計算出每個決策的期望效用值 (在假設其他代理人也遵循賽局理論的最佳行動的條件下)。

2. 機制設計:

當多個代理人同處於一個環境中時,也許可能定義環境的規則(也就是代理人必須參與的遊戲), 使得當每一個代理人都採用賽局理論給出的、

能最大化自己的效用的解時,所有代理人的集體利益也最大化。

單步賽局

我們從考慮賽局的一些限制集合作為開始:所有玩家同時地執行行動,且賽局的結果是基於此行動的單一集合。(實際上

它並非關鍵性,行動正好發生在同時間。不管任何玩家都不知道其他玩家的選擇)。

● 制定決策的遊戲者(player)或者代理人。

● 每個遊戲者可以選擇的行動(action)。

● 收益函數(payoff function)給出了所有遊戲者在每種行動組合情況下各自的效用值。

戰略形式(也稱為普通形式)

戰略

純戰略(pure strategy)

混合戰略

戰略配置(strategy profile)

結果(outcome)

囚犯難題

優勢戰略(dominant strategy)

絕對優於(strongly dominate)

相對優於(weakly dominate)

巴烈圖最佳化(Pareto optimal)

巴烈圖劣於(Pareto dominated)

優勢戰略均衡(dominant strategy equilibrium)

均衡(equilibrium)

局部最佳

納許均衡(Nash equilibrium)

重複的賽局

協調遊戲(coordination game)。

零和遊戲(zero-sum game)

極大極小(maximin)

極大極小均衡(maximin equilibrium)

線性規劃

重複性賽局

目前為止,我們只看到持續一步的遊戲。最簡單的多步遊戲是重複性賽局(repeated game),其中

遊戲者重複地面對同樣的選擇,不過每次都知道關於所有遊戲者以前的選擇歷史的知識。對於重複

性遊戲的戰略配置指定了每個遊戲在每個時刻對於每個可能的過往歷史的一個行動選擇。和MDP一樣

,收益是隨時間累加的。

永久性懲罰(perpetual punishment)。

針鋒相對(tit-for-tat)

循序賽局

在一般的例子,賽局是由一連串的回合組成,其中不需完全一樣。如此的賽局最好的表示方法

是遊戲樹(game tree),其中博弈學家稱之為廣泛形式。

完全的回憶(perfect recall)

信念狀態

資訊集合

循序形式(sequence form)

抽象化

古諾競爭理論(Cournot competition)

行動

沒有個簡便的方法展現一個賽局,其中玩家必須發現那些行動是存在的。

戰略

博弈論在表達想法是非常優越,其中其他玩家的戰略是初期未知的──只要我們假設所有代理人是理性的。

機會

若賽局是依據擲一個骰子,它是很容易透過結果的均勻分佈來塑模機會節點。

效用

若不知道我們敵手的效用呢?再次,它可用機會節點塑模,像是其他代理人在每個分支知道自己的效用,但我們不是。

機制設計

在前一節中,我們問:「給定一個遊戲,什麼是理性戰略?」。在本節中,我們要問「如果代理人是理性的,我們應該設計什麼樣的遊戲?」。

更具體地說,我們要設計這樣的遊戲,她的解由每個代理人尋求自己的理性戰略所組成,能導致某個全局效用函數的最大化。

機制設計(mechanism design)

逆賽局理論

機制

核心

拍賣

讓我們首先考慮拍賣。拍賣是一個銷售某些貨物給一群投標者的成員的機制。

私人價值

共同價值

遞增叫價拍賣(ascending-bid)

英式拍賣(English auction)

保留價

優勢戰略

戰略免疫(strategy-proof)

揭露真相或真實

激勵相容

啟示原理

密封投標拍賣(sealed-bid auction)

密封投標次高價拍賣(second-price sealed-bid auction)

vickrey 拍賣

最高價

收入等價理論

共同商品

現在我們考慮另一個類型的賽局,其中每個國家都制定了他們對於控制空氣汙染的法規。

公有的悲劇(the tragedy of the commons)

外在性(externality)

Vickrey-Clarke-Groves 或 VCG

總結

本章顯示了如呵使用關於世界的知識進行決策,即使行動的結果是不確定的以及行動的回報可能直到

很多行動完成以後才會兌現。要點如下:

● 在非確定的環境中的循序決策問題,也稱為馬可夫決策過程,或稱MDP,是透過指定行動的機

率結果的轉移模型和指定每個狀態回報的回報函數而定義的。

● 狀態序列的效用是序列上所有回報的總和,其中回報有可能隨時間而進行折扣。一個MDP的解

是一個把決策與代理人可能到達的每個狀態聯繫在一起的策略。最佳策略最大化當它執行時遇

到的狀態序列的效用。

● 狀態的效用是從這個狀態開始執行最佳策略時遇到的狀態序列的期望效用值。價值疊代演算法

透過對把每個狀態的效用與其鄰接狀態的效用關聯起來的方程組進行疊代求解,以解決MDP。

策略疊代交替執行用當前策略計算狀態的效用和用當前的效用改進當前的策略。

● 部分可觀察的MDP或者簡寫為POMDP,比MPD的求解困難得多。他們可以透過轉化成一個

信念狀態的連續空間中的 MDP 來解決 ,價值疊代和策略疊代演算法都已經被設計出來。

POMDP中的最佳行為包括用資訊收集來減少不確定性,並因此在未來制定出更好的決策。

● 決策理論代理人可以在POMDP的環境中進行構建。代理人用動態決策網路表示轉移模型和觀察模型

,更新他的信念狀態,並向前投影可能的行動序列。

賽局理論描述了再多個代理人同時相互影響的情景下代理人的理性行為。遊戲的解是滿足納許均衡

的戰略配置,其中沒有代理人具有偏離指定戰略的動機。

機制設計可以用於設定代理人交互的規則,從而透過作為個體的理性代理人的操作最大化某個

全局效用。有時候,存在不需要每個代理人考慮其他代理人的選擇而時做這個目標的機制。

我們將在第 21 章中回到 MDP 和 POMDP 的世界,當我們研究允許代理人根據再循序的、不確定的

環境中得到的經驗來改進自己的行為的強化學習演算法時。