2

我已经开始玩强化学习(使用 Sutton 的书)。我无法完全理解必须减少马尔可夫状态空间而另一方面又不对重要和不重要的假设之间的悖论。

背景

例如。以跳棋为例,Sutton 表示不应将奖励分配给游戏中的某些动作,例如击败对手的棋子。他声称这可能会优化 AI 以获取棋子而不是赢得比赛。因此,奖励应该只给予您想要达到的结果(例如赢得比赛)。

问题 1

假设一个(德州扑克)扑克 AI 的马尔可夫状态只有玩家的手和桌上的牌。这大约有 52*51*50*49*48*47*46/1*2*3*4*5*6*7 状态。现在假设我们希望 AI 将玩家的资金池 + 他们的赌注考虑在内。如果我们假设 8 个玩家每人拥有 1-200.000 美元,这将使马尔可夫状态空间接近“无限数量的组合”。

问题2

一种减少状态的策略可能是将玩家现金分为穷人中等人或富人。这严重减少了我们的状态空间,但是,我怎么知道 a) 3 个组就足够了?b) 每组的区别限制是什么?

干杯,

4

3 回答 3

3

一般的方法是在状态空间变得太大时使用函数逼近来减少状态空间。这里的关键是你在相似的状态之间推广奖励。当然,这需要您通过利用领域知识提出有意义的功能。不幸的是,没有任何算法可以同时解决特征选择问题和控制问题以及任何关于最优性的保证(在多项式时间内),我们也不希望发明任何算法。

为了回答您的问题,1) 即使是在 8 人限制德州扑克中的初学者级别表现也远远超出了当前最先进的研究水平。在http://poker.cs.ualberta.ca/上查看当前“世界上最好的电脑扑克玩家”研究。也就是说,您可以尝试将空间划分为任意特征,例如: (player[1].cash > 1000) 0:1 、 (player[1].cash > 2500) 0:1 等。

2)很难知道你的表现有多好,通常人们只是运行它,直到它开始收敛,然后看看它的表现如何......

于 2011-02-15T22:54:16.733 回答
2

一种减少 RL 中状态空间的建议方法是使用状态-动作层次结构。您可以将其分解为更小的变量,例如 x1、x2、x3,而不是使用单个状态变量 X。然后您测量它们的转换频率并确定它们之间的依赖关系(例如,当 x2=abc 时 x1 通常会发生变化)。然后,您可以制定一个策略,解释如何最好地转换变化较快的变量,以更改变化较慢的变量,从而最大化奖励。

这种方法仍然相对较新,我不知道它有任何公开的实现。然而,有几篇论文提出了可能的实现。MAXQ算法假定人为定义的层次结构,而HEXQ 算法描述了学习层次结构和策略的方法。

于 2011-02-16T01:09:35.093 回答
1

补充@fairidox 点(我同意):如果玩家的现金底池在 1-200000 之间,那么按照他们所说的给定函数近似值,如果玩家处于拥有 1000 美元或 1001 美元的状态。现在,正如您在问题 2 中提到的,选择这些任意边界存在问题。

相同的逻辑适用于将机器人置于物理空间中,其在一个空间中的状态可能与右侧 1mm 的状态具有相同的值。如果我们没有近似,那么我们可能会争辩说我们也应该为 0.5mm、0.25mm 等设置一个新状态。Sutton 和 Barto(以及 David Silver 的讲座)为此讨论了 Tile Coding,我认为这也可能适合您的扑克的例子。

于 2020-05-27T22:36:12.570 回答