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