線性 MDP 理論（linear MDP theory）

在表格式 MDP 中，樣本成本隨狀態的原始數量成長，當狀態多達數十億時這毫無希望。線性 MDP 理論靠假設隱藏結構來挽回可解性：轉移動態與報酬可以寫成「狀態–動作對上已知特徵向量」的低維線性函數。若此成立，學習就活在 d 維特徵空間中，而非龐大的狀態空間。

在線性 MDP 假設下，轉移核與報酬都對特徵映射 φ(s,a) 線性，而關鍵在於：每個策略的動作價值也都變成對同一組特徵線性。LSVI-UCB 之類的演算法會加上一個由特徵協方差矩陣算出的樂觀獎勵項，換來隨特徵維度 d 與視界變化、完全不依賴狀態數量的後悔界。這就是回報：結構把一個不可解的計數轉成 d 的多項式。

這個模型很受限——真實特徵很少讓動態恰好線性——而且分析很細膩，因為獎勵項必須同時控制所有狀態的誤差。線性 MDP 最好被理解為「函數近似可被證明有效」的最簡設定，是邁向一般理論的踏腳石。