ICLR 2024：確定性與隨機(jī)環(huán)境中的effective horizon！ 原創(chuàng)
現(xiàn)有的大多數(shù)強(qiáng)化學(xué)習(xí)理論無法解釋實際強(qiáng)化學(xué)習(xí)算法何時或為何有效：理論家分析不同的算法并做出在真實環(huán)境中不一定成立的假設(shè)。這使得將理論洞察力應(yīng)用于實踐變得困難或不可能。
為了找到在常見環(huán)境中成立的假設(shè)，研究人員構(gòu)建了一個名為BRIDGE的數(shù)據(jù)集，包含來自Atari和Procgen等基準(zhǔn)測試中155個確定性MDP完整的表格表示，其中一些MDP具有1000萬個以上的狀態(tài)！
研究人員發(fā)現(xiàn)超過2/3的MDP具有一個令人驚訝的屬性：在隨機(jī)策略下具有最高Q值的動作，在最優(yōu)策略下也具有最高的Q值。值得注意的是，當(dāng)這種情況成立時，PPO更有可能找到最優(yōu)策略。
研究人員將這一特性推廣為一種新的MDP復(fù)雜度度量，稱之為effective horizon，它大致對應(yīng)于當(dāng)葉節(jié)點使用隨機(jī)模擬進(jìn)行評估時，需要多少步的前瞻搜索來確定下一個最優(yōu)動作。
例如，下面的左側(cè)MDP具有非常稀疏的獎勵，因此effective horizon H不會比完整平線T短。然而，右側(cè)的MDP具有非常密集的獎勵，其effective horizon只有1。這反映了人們的直覺，即密集的獎勵使得強(qiáng)化學(xué)習(xí)更容易。
利用BRIDGE中的MDPs，研究人員評估了深度強(qiáng)化學(xué)習(xí)算法PPO和DQN，并將它們的樣本復(fù)雜度與可證明的界限進(jìn)行了比較。基于effective horizon的新界限極具預(yù)測性！
Effective horizon可以解釋獎勵塑造和使用預(yù)訓(xùn)練策略初始化這兩種常用工具對提高強(qiáng)化學(xué)習(xí)性能的益處。
隨機(jī)環(huán)境
隨機(jī)環(huán)境更難分析，因為強(qiáng)化學(xué)習(xí)算法可能需要對從未見過的狀態(tài)進(jìn)行泛化。在實踐中，這需要神經(jīng)網(wǎng)絡(luò)函數(shù)逼近器，并且以前的強(qiáng)化學(xué)習(xí)理論無法解釋為什么使用神經(jīng)網(wǎng)絡(luò)進(jìn)行高效的強(qiáng)化學(xué)習(xí)是可能的。
在對確定性環(huán)境的工作中，通過分析一種名為GORP的算法來回避了這個問題，該算法僅學(xué)習(xí)一系列動作，無需神經(jīng)網(wǎng)絡(luò)。GORP通過在隨機(jī)策略的Q值的蒙特卡洛估計上貪婪地執(zhí)行動作來逐步構(gòu)建動作序列。
為了將這一方法擴(kuò)展到隨機(jī)環(huán)境中，研究人員用隨機(jī)演算過程中收集的（狀態(tài)、動作、未來獎勵）三元組來進(jìn)行隨機(jī)策略Q函數(shù)的回歸，以取代對隨機(jī)策略Q值的簡單均值估計。
研究人員引入了一種名為SQIRL的算法，它使用神經(jīng)網(wǎng)絡(luò)對隨機(jī)策略的Q函數(shù)進(jìn)行回歸，應(yīng)用1或2步的擬合Q迭代，然后采用貪婪策略。盡管它很簡單，但在像Atari的粘滯動作等基準(zhǔn)測試中，SQIRL的表現(xiàn)與PPO和DQN幾乎相當(dāng)好！
研究人員還對SQIRL進(jìn)行了理論分析。結(jié)果表明，只要有效視野較低，任何具有低IID泛化誤差的回歸算法都可以在SQIRL中用于高效的強(qiáng)化學(xué)習(xí)。這解釋了為什么能夠進(jìn)行IID泛化的神經(jīng)網(wǎng)絡(luò)在深度強(qiáng)化學(xué)習(xí)中也表現(xiàn)出色！
論文：https://arxiv.org/abs/2312.08369
代碼：https://github.com/cassidylaidlaw/effective-horizon
本文轉(zhuǎn)載自公眾號AIGC最前線
