Neural Fictitious Self Play——从博弈论到深度强化学习

近期阅读 UCL Johannes Heinrich 和 David Silver 关于博弈的均衡求解论文,我发现他们给出的方法实际上是一种比较强大且通用的技术,有必要深入研究一下。对这篇文章的解读,不得不提的是他们和在 2015 年的前篇。在那里对基础内容似乎讲解的更加详细。然而,由于其工作的交叉领域中各自的术语差异较大,所以在理解论文时会造成一定的麻烦,本文期望从 NSFP 出发完整地分析涉及到的相关领域中的问题,结合算法谈谈如何使用这项新的技术来解决若干领域中的有趣问题。

前期是为了理解所以大部分内容是直接翻译该论文的工作。计划在今后细化讲解,争取把这一套方法完整地展示清楚。

NFSP 就是引入神经网络近似函数的 FSP,是一种利用强化学习技术来从自我博弈中学习近似纳什均衡的方法。解决了三个问题:

  1. 无先验知识 NFSP agent 学习
  2. 运行时不依赖局部搜索
  3. 收敛到自我对局的近似纳什均衡

这是一般的不完美信息二人零和博弈。虚拟对弈同样也会收敛到合作、势力场博弈的纳什均衡。所以 NFSP 也能够成功应用在这些博弈上。另外,近期的研究关于连续空间行动的强化学习(Lillicrap et al. 2015)也能够应用在连续行动博弈中,目前的博弈论方法并不能直接处理这样的情形。

然而我们需要知道了解相关的基础,才能够真切地了解这篇文章给我们带来了什么启发。本文在对原文理解基础上进行翻译,后续会继续增加向前的回溯和向后的扩展。

强化学习

首先是强化学习基础。强化学习中的 agent 需要学会通过和环境交互中最大化自己的期望未来回报。一般来说,环境会被建模为一个 MDP。

很多强化学习算法从序列化经验中学习。这些经验的形如 (st,at,rt+1,st+1),其中的 st 是在时间 t 的状态,at 是在那个状态下选择的行动,rt+1 是之后的回报,st+1 是转移的下一个状态。常见的目标函数是学习 行动-值函数,Q(s,a) = Eπ[Gt|St=s, At=a],定义为在状态 s 采取行动 a 并采取策略 π 的期望收益。
on-policy 学习是指 agent 学习当前采用的策略。off-policy 学习则是 agent 从另一个 agent 或者另一个策略(如之前的策略)的经验中学习。

Q-learning 是一种 off-policy 学习方法。其学习的是贪婪策略,在每个状态下,都会选择有最高的估计值的行动。通过应用 off-policy 强化学习方法在 respective 转移元组来存储和回放过去的经验的方法称为经验回放。Fitted Q Iteration (FQI)是一种采用经验回放的 Q-learning 的批量强化学习方法。Neural Fitted Q Iteration(NFQ)和 Deep Q Network(DQN)则分别是在批量和在线更新的 FQI 两种扩展。

展开式博弈

这是一类包含多个参与人的序列化交互的模型。参与人的目标是最大化自身的收益(payoff)。在不完美信息博弈中,每个参与人只会观察到自身的信息状态(information state),例如,在扑克游戏中,玩家只会知道自己私有的牌,并不知道其他人的。每个参与人会选择行为策略(behaviourial strategy)将信息状态映射到可选的行动的概率分布上。我们假设博弈是有完美回忆(perfect recall)的,每个参与人当前信息状态 sti 暗含了他自己的导致达到当前状态的信息状态和行动序列,s1i,ati,s2i,a2i,…,sti。realisation-probability,xπi (sti) = Πk=1t-1 πi(ski, aki),给出了参与人 i 行为策略 πi 对实现他信息状态的 sti 的概率。策略组合(strategy profile)π = (π1,…,πn) 是对所有参与人策略的集合。π-i 则是除去 πi 之外的 π 中的策略。给定一个固定的策略组合 π-i,参与人 i 在这个设置下任何达到最优的收益都是一个最优反应(best response)。近似反应或者 ϵ-最优反应是不超过ϵ 的亚最优。纳什均衡是一个策略组合,其中每个参与人的策略都是对其他策略的最优策略。而近似纳什均衡或者ϵ-纳什均衡就是ϵ-最优反应的策略组合。由于在纳什均衡中没有参与人可以通过策略的偏移来提升自己的收益。所以,纳什均衡可以被当成理性自我对局学习的不动点。实际上,纳什均衡是唯一个理性 agent 在自我对局中可以收敛的策略组合。

虚拟自我对局 Fictitious Self Play, FSP

虚拟对局是从自我对局中学习的博弈论模型。自我对局的参与人选择针对其对手的平均行为的最佳反应。自我对局参与人的平均策略在某些类型的博弈(如二人零和博弈和多人势力场博弈)中都会收敛到纳什均衡。Leslie 和 Collins 在 2006 年给出了推广的弱化自我对局。这种模型和通常的自我博弈有着类似的收敛保证,但是允许有近似最优反应和扰动的平均策略更新,也让这个扩展模型对机器学习尤其合适。

自我对局通常使用规范式博弈定义,这与扩展式博弈在有效性上存在指数级差距。Heinrich 等人在 2005 年引入了 Full-Width Extensive Form FSP(XSP),可以让自我对局参与人使用行为式,扩展式进行策略更新,得到了线性的时间和空间复杂性。这里一个关键的洞察是对规范式策略的凸组合,σ-nf= λ1 π-nf1 + λ2 π-nf2,我们可以达到一个实现等价的行为策略 σ,通过设置该值为成比例于对应的实现概率的凸组合,

\sigma(s,a) \propto \lambda_1 x_{\pi_1}(s) \pi_1(s,a) + \lambda_2 x_{\pi_2}(s)\pi_2(s,a) \forall s, a, (1)

其中 λ1xπ1(s) + λ2xπ2(s) 是在信息状态 s 的策略的规范化常量。除了在行为策略下定义自我对局的 full-width 平均策略更新外,公式(1) 给出了从这样的策略的凸组合中采样数据集的一种方法。Heinrich 等人在 2015 提出了 Fictitious Self Play (FSP)的基于采样和机器学习的算法来近似 XFP。FSP 分别用强化学习和监督学习来替换最优反应计算和平均策略更新。特别地,FSP agent 产生他们在自我对局中的经验转换的数据集。每个 agent 存放了自身的转移元组 (st,at,rt+1,st+1) 在记忆 MRL 中 ,这个为强化学习设计。而 agent 自身的行为 (st,at) 被存放在另一个分开的记忆 MSL 中,这为监督学习设计。自我对局的采样通过 agent 的强化学习的记忆来近似用其他参与人的平均策略组合定义的 MDP 的数据。因此,通过强化学习的 MDP 的近似解会产生一个近似的最优反应。类似地,agent 的监督学习记忆近似了 agent 本身的平均策略,这可以通过监督式的分类方法学习。

神经网络虚拟自我对局

进行了多种扩展:神经网络函数近似,reservoir 采样,anticipatory 动态性和完全基于 agent 方法。NFSP agent 和博弈中的其他参与人进行交互,并记住自身关于博弈状态转移的经验和自身的行为。NFSP 将这些记忆分成两个数据集——一个给深度强化学习,一个给监督学习使用。特别地,这个 agent 从 MRL 的数据中使用 off-policy 强化学习训练一个神经网络 FQ 来预测行为值,Q(s,a)。得到的网络定义了 agent 的近似最优策略 β = ε-greedy(FQ),这里根据概率 ε 选择随机行动,根据概率 1 – ε 选最大化预测行为值的行动。NFSP agent 训练了另外一个神经网络,FS 在 MSL 的数据中使用监督学习来模拟自己过去的行为。这个网络将状态映射到了行动概率上,定义了 agent 的平均策略,π = FS。在博弈进行过程中,agent 从两个策略 β 和 π 的混合中选择策略。

尽管虚拟参与人通常是针对对手的平均策略进行最优反应,但在连续时间的动态虚拟对局参与人是对对手平均规范式策略 π-nft-i + η d/dt π-nft-i短期预测的最优反应。研究表明,选择合适的,博弈相关的 η 可以提高在均衡处的自我对局的稳定性。NFSP 使用 β-nft+1i– π-nfti ≈ d/dt π-nfti 作为用在 anticipatory 动态中的离散时间导数近似值。注意 Δ π-nfti ∝ β-nft+1i – π-nfti 是常见的离散时间自我对局的规范化更新方向。为了让一个 NFSP agent 计算近似对对手预测平均策略组合 σ-i ≡ π-nf-i + η(β-i– π-nf-i)的最优反应, βi,agent 需要迭代求值并最大化其行动值,Q(s,a) ≈ Eβi-i[Gti|St=s, At=a]。这个可以使用 off-policy 强化学习,如 Q-learning 或者 DQN 在和对手的预测策略,σ-i 对局的经验上获得。为了确保 agent 的强化学习记忆,MRL,包含这种类型的经验,NFSP 需要所有的 agent 从 σ≡ (1 – η)π-nf + η (β-nf)选择他们的行动,其中 η ∈ R 被称为预测参数(anticipatory parameter)。

虚拟自我对局通常要保留平均规范式博弈的最优反应策略,π-nfTi = 1/T Σt=1T βti。Heinrich 等人在 2015 年给出了使用采样和机器学习技术来产生数据并学习用展开式博弈形式表示的规范式博弈策略凸组合。例如,我们可以通过使用 βti, t = 1,…,T 按照 1/T 的比例来采样整个博弈的过程来产生展开式数据。NFSP 使用 revervoir 采样来记忆其平均最优反应的经验。agent 的监督式学习记忆,MSL 是一个 reservoir 仅仅会在采用其近似最优策略 β 时增加经验。NFSP agent 通常会训练自己的平均策略网络 π=FS来匹配其存储在自身监督学习记忆中的平均行为,例如通过优化过去行为的对数概率来进行训练。算法 1 给出了 NFSP,其中使用 DQN 作为强化学习的方法。

神经网络虚拟自我对局 NFSP 算法


输入:

  1. Γ {Game}
  2. MRL, MSL {RL and SL memories}
  3. FQ, FS {Action value and policy networks}
  4. β = ε-GREEDY(FQ) {Best response policy}
  5. π = FS {Average policy}
  6. σ {Current policy}

输出: π an approximate Nash equilibrium in self-play


function STEP():

  1. st,rt,ct ←OBSERVE(Γ)
  2. at ←THINK(st,rt,ct)
  3. ACT(Γ,at)

end function


function THINK(st, rt, ct)

  1. if ct = 0 {episode terminated} then
    σ ← SAMPLEPOLICY(β, π)
    end if
  2. if st-1 ̸= nil then
    τt ←(st-1,at-1,rt,st,ct)
    UPDATERLMEMORY(MRL, τt)
    end if
  3. at ← SAMPLEACTION(σ)
  4. if σ = β then
    UPDATESLMEMORY(MSL, (st, at))
    end if
  5. st−1 ← st
  6. at−1 ← at
  7. β ← REINFORCEMENTLEARNING(MRL)
  8. π ← SUPERVISEDLEARNING(MSL)

end function


function REINFORCEMENTLEARNINIG(MRL)

  1. FQ ← DQN(MRL)
  2. return ε-GREEDY(FQ)

end function


function SUPERVISEDLEARNING(MSL)

  1. FS ← Apply stochastic gradient descent to loss:
    E(s,a)∼MSL[−logπ(s,a)]
  2. return FS

end function

参考

  1. http://arxiv.org/abs/1603.01121
  2. http://jmlr.org/proceedings/papers/v37/heinrich15.pdf
Advertisements

采用双 Q-学习的深度强化学习技术

为了解决序列决策问题,我们可以学习每个行动的最优值的估计,即采取该行动并根据后续最优策略的未来回报的期望和。在一个给定策略 \pi,在状态 s 的行动 a 的真实值为 Q_{\pi}(s, a) \equiv \mathbb{E} [R_1 + \gamma R_2 + \dots | S_0 = s, A_0 = a, \pi ],其中 \gamma \in [0, 1] 是折扣因子。最优值就是 Q^* (s, a) =\max_{\pi} Q_{\pi}(s, a)。最优策略就可以通过在每个状态选择最高值的行动给出。

最优行动值的估计可以通过 Q-学习获得 (Watkin, 1989),这也是一种形式的即时差分学习 (temporary difference) 学习 (Sutton, 1988)。大多数有趣的问题涉及遍历的状态空间太大使得学习所有的行动值难以进行。所以,我们可以通过学习一个参数化的值函数 Q(s,a;\theta_t)。标准的Q-学习在状态S_t 下进行行动A_t 更新参数,观察及时回报 R_{t+1} 和结果状态S_{t+1} 变成:

\theta_{t+1} = \theta_t + \alpha (Y_t^Q - Q(S_t,A_t;\theta_t)) \nabla_{\theta_t}Q(S_t,A_t;\theta_t) .(1)

其中 \alpha 就是标量的步长,目标 Y_t^Q 定义如下:

Y_t^Q \equiv R_{t+1} + \gamma \max_{a}Q(S_{t+1},a;\theta_t).(2)

类似于 SGD,将当前的值 Q(S_t, A_t; \theta_t) 更新为目标值 Y_t^Q

深度 Q 网络

深度 Q 网络 是多层神经网络,给定状态 s 输出一个行动值的向量  Q(s,.;\theta),其中 \theta 是网络的参数。对一个 n- 维状态空间和一个包含 m 个行动的行动空间,该神经网络是从 R^nR^m 的映射。 DQN 算法的两个最重要的特点是目标网络 (target network) 和经验回顾 (experience replay)。目标网络,其参数为 \theta^-,其实除了其参数每 \tau 次从在线网络复制外都和在线网络相同,所以\theta^-_t = \theta_t,在其他步都是固定大小。DQN 使用的目标就是:

Y_t^{DQN}\equiv R_{t+1} + \gamma \max_{a}Q(S_{t+1},a;\theta_t^{-1}).(3)

对经验回顾,观察到的转换被存放一段时间,并会均匀地从记忆库采样来更新网络。目标网络和经验回顾都能大幅提升算法的性能 (Mnih et al., 2015)。

双 Q- 学习

公式 (2) 和 (3) 中,在标准的 Q-学习和 DQN 中的 \max 操作使用同样的值来进行选择衡量一个行动。这实际上更可能选择过高的估计值,从而导致过于乐观的值估计。为了避免这种情况的出现,我们可以对选择衡量进行解耦。这其实就是双 Q-学习 (van Hasselt, 2010)。

最初的双 Q- 学习算法中,两个值函数通过将每个经验随机更新两个值函数中的一个,这样就出现了两个权重集合,\theta 和 \theta'。对每个更新,一个权重集合用来确定贪心策略,另一个用来确定值。为了更好地比较这两者,我们可以将 Q-学习中的选择和衡量分解,将 (2) 重写为:

Y_t^Q = R_{t+1} + \gamma Q(S_{t+1}, argmax_{a} Q(S_{t+1},a;\theta_t);\theta_t).

Q- 学习误差可以被写成:

Y_t^{DoubleQ} \equiv R_{t+1} + \gamma Q(S_{t+1}, argmax_{a} Q(S_{t+1},a;\theta_t);\theta_t'. (4)

注意到在 argmax 中行动的选择仍旧取决于在线的权重 \theta_t。这表示,如同Q- 学习中那样,我们仍然会根据当前值来估计贪心策略的值。然而,我们使用了第二个权重集合 \theta'_t 来公平地衡量这个策略的值。第二个权重的集合可以对称式地通过交换 \theta 和 \theta' 的更新。

Why Deep Learning Works II: the Renormalization Group

Deep Learning is amazing.  But why is Deep Learning so successful?  Is Deep Learning just old-school Neural Networks on modern hardware?  Is it just that we have so much data now the methods work better?  Is Deep Learning just a really good at finding features. Researchers are working hard to sort this out.

Recently it has been shown that [1]

Unsupervised Deep Learning implements the Kadanoff Real Space Variational Renormalization Group (1975)

This means the success of Deep Learning is intimately related to some very deep and subtle ideas from Theoretical Physics.  In this post we examine this.

Unsupervised Deep Learning: AutoEncoder Flow Map

An AutoEncoder is a Unsupervised Deep Learning algorithm that learns how to represent an complex image or other data structure $latex X $.   There are several kinds of AutoEncoders; we care about so-called Neural Encoders–those using Deep Learning techniques to reconstruct the data:

recon

The simplest Neural Encoder…

View original post 2,232 more words

Streaming Median

Math ∩ Programming

Problem: Compute a reasonable approximation to a “streaming median” of a potentially infinite sequence of integers.

Solution: (in Python)

DiscussionBefore we discuss the details of the Python implementation above, we should note a few things.

First, because the input sequence is potentially infinite, we can’t store any amount of information that is increasing in the length of the sequence. Even though storing something like $latex O(log(n))$ integers would be reasonable for the real world (note that the log of a petabyte is about 60 bytes), we should not let that stop us from shooting for the ideal $latex O(1)$ space bound, and exploring what sorts of solutions arise under that constraint. For the record, I don’t know of any algorithms to compute the true streaming median which require $latex O(log(n))$ space, and I would be very interested to see one.

Second, we should note the motivation for…

View original post 388 more words

Mapping WordPress Posts to Elasticsearch

greg.blog

I thought I’d share the Elasticsearch type mapping I am using for WordPress posts. We’ve refined it over a number of iterations and it combines dynamic templates and multi_field mappings along with a number of more standard mappings. So this is probably a good general example of how to index real data from a traditional SQL database into Elasticsearch.

If you aren’t familiar with the WordPress database scheme it looks like this:

These Elasticsearch mappings focus on the wp_posts, wp_term_relationships, wp_term_taxonomy, and wp_terms tables.

To simplify things I’ll just index using an English analyzer and leave discussing multi-lingual analyzers to a different post.

A few notes on the analyzers:

  • The minimal_english stemmer only removes plurals rather than potentially butchering the difference between words like “computer”, “computes”, and “computing”.
  • Lowercase keyword analyzer makes doing an exact search without case possible.

Let’s take a look at the post mapping:

Most of the…

View original post 379 more words

The Strange Ruby Splat

End of Line

This article has been republished on Monkey and Crow.

As of ruby 1.9, you can do some pretty odd things with array destructuring and splatting. Putting the star before an object invokes the splat operator, which has a variety of effects. First we?ll start with some very useful examples, then we will poke around the dark corners of ruby?s arrays and the splat operator.

Method Definitions

You can use a splat in a method definition to gather up any remaining arguments:

In the example above, what will get the first argument, then *people will capture however many other arguments you pass into say. A real world example of this can be found in the definition of Delegator#method_missing. A common ruby idiom is to pass a hash in as the last argument to a method. Rails defines an array helper Array#extract_options! to make this idiom easier to…

View original post 328 more words

乱弹

最近天天想写下自己的感受,在实验室的办公桌前,在家中的硬板床上,在颠簸的公车里,在轰鸣的地铁中。最喜欢的就是使用简书了,用手机浏览器访问然后开始写东西。我知道这不是一般意义的写作,这是一种情感的宣泄,一种思考的凝结。就在今年,突然增加这种冲动。

生活带来了给我们思考的导火索。可以是人,也可以是一件事情,一个食物,一个景点。

写着写着,就会忘却自己的最初的想法,策马奔腾到天外。

BGP subgraph

写作需要冲动,这句话是听道哥讲的,现在能够清楚地感受到来自心底最原始和狂野的激情,带着理性的影子,冲开重重的枷锁,出现在我双手的指尖,从而进入计算机的屏幕。我能够深刻地了解到这整个过程,使用文字的一整个过程。计算机的原理,我也略微清楚的知道。我在使用Chrome浏览器,连着简书的网站服务器,之间不断地通过网络进行互联。最先是wifi无线链接着本地的路由器,然后连到学校的网络中心的路由器,接着连出去。中间不知道有多少装着各式各样的网络设备帮助我完成这个过程。他们就如同一个人的各类神经,器官,数据便是通道中的血细胞或其他物质,整个进行一种繁忙的交互。

尽管我看不到,但是我明白,当我们在写东西的时候,整个自己和环境完成了的一种交流,这个过程中有物理的工具,有情识的发挥,有情感的流露。突然发觉,这才是我最想要的东西。

逻辑、计算机原理、思考过程、情感表达、语言使用。如何精准地表达自己,是逻辑最初的目标。表达清楚了,才能进行下一步的证明。完成整个理论的架构。而计算机的构建,本质上仍是逻辑理论的延续。不管怎样,我们都应该认识到这一点。人和计算机是不一样的。(至少现在看来,AI只能是人的一种工具)

冲动是一种魔力,能够激发人心底的原始的过程。这些东西在潜意识中进行。然后保存下来。通过冲动,把他们激发出来。真是一种好棒的感觉。

Catster_LetsTalk_hero_17 Dogster_LetsTalk1_2人,需要去交流,有时候其他人不经意的一句话,都能够激起你内心深处高高的浪头。我想,对话和读书的作用就是这个。我们并不需要去将其他人身上发生的故事记下来,然后自己去扮演那些故事中的角色。而是用这些书中的故事,人物的言语,作者的情感,来激发我们的想像力和创作力。

每个生命都是美妙的过程。我们有幸生活一次,那真的是莫大的荣幸!

突然安静

给一个小小的房间,让喜欢的音乐围绕自己。
内心的涌动暂歇,湿润了我们的眼睛的泪滴凝结成冰。
生命列车的飞驰而过,让这些美好的东西尽现珍贵。
对过去说再见,因为永远也见不到了,那就忘却吧。
拍拍身上的灰,系好鞋带,微风中前行。
不要被过去所累。也不须惊怖于未来。就是现在。

Image