谷歌DeepMind公司研发的AI围棋AlphaGo在去年嗨翻天的时候，让我觉得现在的机器学习学习技术真的很NB，因为自己的专业，私下一直有关注机器学习在量化投资这块的一些实践。昨天看到广发出了一篇名为《虚拟遗憾最小化应用于量化择时与交易》的文章，让我眼前一亮，感觉这都怎么了啊。但是看到最后的结果，也不是很理想。这样看来，也是情理之中。很多高大上的东西，要放在金融市场去真正赚钱，这倒不见得会有多么好。除了市场本身外，自身的研究水平也是一方面。经常听朋友说，大道至简，其实也是蛮有道理的。无论什么模型，最终能够持续盈利，才是一个良好发展取向，但是不妨碍我们在量化投资的道路上的探索前行！
今天就来学习一下这篇文章，部分内容来自报告本身，部分是我自己整理总结的。
好了，话不多少，让我们来见识一下虚拟遗憾最小化（CFR）吧！
一
BlackRock(贝莱德)创始人及首席执行官：
“信息的民主化使得主动性投资变得越来越难做。我们必须改变生态系统，更多地依赖大数据、人工智 能、量化等手段”。
德州扑克是一项标志情商、智慧和勇气的牌类游戏，自20世纪初诞生便风靡全球，深受各个不同职业群体玩家的青睐。德州扑克和围棋的一个主要不同在于：围棋是一种“完美信息”博弈，即对于玩家而言，游戏中所有的信息都已经在棋局中体现出来；而德州扑克是一种“不完美信息”博弈， 游戏玩家并不知道游戏中所有的信息，比如对手的手牌和桌上未翻开的公共牌，存在隐藏的信息，同时还有诈唬等心理战术。这些特点使得德州扑克更贴近生活中真实的拍卖、谈判等金融政治博弈场景，所以德州扑克也许是测试人工智能是否能够应付这些情景的一个平台。
2017年1月,卡内基梅隆大学人工智能机器人Libratus与四位更强的人类职业德扑玩家进行为期20天，共12万手的比赛，共计领先人类团队176万美元的虚拟筹码。2017年4月，创新工场李开复邀请Libratus与2016世界德扑大赛WSOP金手链冠军率领的“龙之队”比赛， 又一次完胜人类选手。而Libratus的开发正是基于虚拟遗憾最小化算法（Counterfactual Regret Minimization）。
由于虚拟遗憾最小化算法的资料不是特别多，我从这里学习到一些知识。大家可以看看（论文太长了，需要花时间去琢磨）：
在这里要学习CRM也是有要求的，你可能需要具备以下的条件：
- 必须深厚的数学功底，能够理解复杂的代码和伪代码。必须有过硬的编程技能和熟悉Java语法和语义。在c 中应该能够遵循Java大部分的例子。
- 要看个资料(Leyton-Brown and Shoham’s “Essentials of Game Theory”, Morgan & Claypool, 2008)。
首先对于一局游戏（如德州），可以把其转化成是一个树状结构。每一个盘面的状态(State)（包括玩家手上的牌，当前的下注等游戏相关信息）都是树的一个节点。在树的每一个节点上，玩家都可以从一系列的动作(Action)中（下注，放弃等）选择一个，然后盘面状态发生转换，从节点A变成节点B。因此每一个当前状态下的可能动作都代表树的一条边。玩家不断的在不同的盘面状态下做决策，使盘面状态发生改变，直到终局（树的叶子节点 Terminate State）。而玩家在当前状态下的决策函数（策略）(strategy)就是当前状态下所有可能动作的一个概率分布。
而每一局游戏，都可以看作是从根节点到叶子节点的一条路径。到叶子节点的时候的最终结果（输或赢了多少钱）就是这局游戏对玩家的效用(utility)。在1v1的游戏中，这是一个零和游戏，即是玩家A和玩家B总的效用为0。
由于这是一个不完全信息的游戏，因此对于没有上帝视角的玩家而言，一些不同的状态(state)给他带了的信息(infomation)是一样的。因此从玩家的角度，所有生成同样的信息的状态可以归为一个集合(infomation set)。
为此CFR的方法是定义了一个Regrets 值，其含义是，在当前状态下，我选择行为A，而不是行为B，后悔的值是多少。
一个简单的例子：在石头剪刀布中，假设对方出剪刀，我也出了布。这个时候，我们会更后悔没有出石头， 相比之下，不会那么后悔出 剪刀。因此一个简单的定义Regrets值的方法是根据最后的效用(utility)。比如在石头剪刀布中，对方出剪刀的情况下，我出布的效用是 -1; 出剪刀的效用是0；出石头的效用是 1，因此我选择布而不是剪刀的后悔值 R（剪刀->布）=1；而不选择石头的后悔值R(石头->布） = 2。
那么怎么用这个值来指导我们进行决策呢？我们可以使用Regret Matching的方法。其本质的思路是，如果在之前的游戏情况中，我们没有选取某一个行为的后悔值最大，那么在下一次我们就更偏向于选择该行为。
比如在剪刀石头布中，如果我们进行了n次游戏，然后把每次游戏没有选取某个行为的后悔值加起来，然后做一个归一化，就可以得到一个概率分布作为我们的策略。而在每一步的后悔值由对手的行为所决定。
可以看出用遗憾匹配计算策略的一个基本思想就是在之前的对局中，自己越后悔没去做的动作，在下一次就有越大的概率执行该动作。这种基于博弈论和心理学的思想，使得算法更加“人性化”。
这是一种比较简单的方式，因此只用进行一次决策，那么对于多次决策问题，就需要使用Counterfactual Regrets了。
首先我们要要记录的就不光是单个的盘面状态，而是整个状态转变的过程，或者是在我们刚刚说到的树状结构中的从根节点到当前节点的整个链路作为状态历史(history)。我们再定义概率 reach probability 为 游戏在某个策略通过这么一个路径走到当前节点的概率。如果有多个路径到达当前节点（不同的状态历史对应同样的信息集），那么当前信息集出现的概率为所有状态历史的reach probability之和。
那么我们怎么计算在当前的一个节点下，可能获得的收益或者叫counterfactual value呢？这个要分两个方面考虑，一个是在当前玩家希望到达的情况下，到达该节点的概率是多少？另一个是，从当前节点走到叶子节点（游戏结束），到达不同的叶子节点的概率是多少？然后我们可以根据叶子节点的效用来计算当前节点的counterfactual value 如下：
其中，s 是使用的策略（概率分布），h是当前的历史（根节点到当前节点的路径）， i代表玩家。P代表概率，u代表效用， t是代表可能的结束的情况（叶子节点）。因此这个式子的含义是基于当前路径h, 当前策略s 的counterfactual_value 是 对所有可能的到达的叶子节点的效用加权求和 。这个权重是根据两个方面计算，第二项比较好理解，是从当前路径h到叶子节点t的概率。第一项是假定当前玩家i在每次选择的时候都选择h对应的行动(Action）从而可以从根节点到达当前路径的概率。因此很显然，counterfactual regret r(h,a) 就被定义为 玩家在当前节点选择了行动a的效用减去其他行动的效用。
最后，和之前的一样，把同一个信息集的状态所对应的regret加起来，就是该信息集的counterfactual regret r(I,a). 然后用前述的Regret Matching的方法就可以更新当前策略了。
CFR的方法的主要思想是把游戏中所有的盘面状态都考虑到，生成一颗完整的状态树。对树的每一个节点都初始化一个策略，然后根据这个策略来玩游戏，这个AlphaGo快速走子有点像。每次都走状态树的一条边，然后根据游戏的结果来更新相关节点的策略。当CFR进行了许多次之后，这个状态树的每条路径都被遍历了很多次，每个节点的策略都被更新趋于纳什均衡了，从而得到一个可以玩游戏的AI。
2.2. 虚拟遗憾最小化
我看到这篇文章：
在这篇论文里，给出了在线虚拟遗憾最小化的框架：
在研报里，是这样描述的：
德州扑克游戏整副牌52张，分四种花色和十三个牌值，玩家数通常是2-10人左右，由两个玩家担任大小盲注先下注。游戏开始时随机为每个玩家分配两张手牌，桌面上有五张未翻开的公共牌。游戏一共进行4次押注，分别是在翻牌前（Pre-Flop）、翻牌（Flop）、转牌（Turn）和河牌（River）阶段。每次押注时，玩家有弃牌（Fold）、跟注（Call）和加注（Raise）三种选择。翻牌阶段翻三张公共牌，转牌和河牌阶段分别再翻一张公共牌。4轮押注结束后进入摊牌阶段，比较未弃牌玩家的手牌和五张公共牌可以组成的最好牌型。
因为局中人不知道对手的手牌、也不知道未翻开的公共牌，所以德扑是不完美信息对称，另外，局中人最多有4次下注机会，所以同时也是扩展式博弈。下图给出了两人（玩家1、玩家2）无限注德州扑克的博弈树，理论上，完整的博弈树包含了游戏的所有情况。图中蓝色和红色的节点表示玩家1和玩家2的决策点H，该决策点到博弈树最上端的点之间的路径称为决策点H对应的动作序列h。绿色的点表示翻开桌上的公共牌；黑色的点表示该玩家的游戏收益或者说是效用值，我们将黑色的点叫做叶子节点Z，就像博弈树末端的叶子，叶子节点Z到博弈树最上端的点之间的路径叫做终止序列z。
两人无限注德州扑克的博弈树
DeepStack是加拿大阿尔伯特大学开发的 人工智能系统。是世界上第一个在 “一对一无限注德州扑克” 上击败了职业扑克玩家的计算机程序。
2017年1月，著名的论文网站 Arxiv 刊发题为《 DeepStack：无限下注扑克里的专家级人工智能》的论文。
如此通过大量的反复迭代，不断更新各个决策点上的策略，就可以使得策略逼近纳什均衡策略，平均虚拟遗憾值达到最小。更新好策略集后，当比赛时再次遇到某一动作序列h时，计算机就会提取该决策点H上的策略，给出执行各个动作的概率。下图给出了虚拟遗憾最小化的算法框架
虚拟遗憾最小化在处理非完美信息、扩展式博弈问题时，能够站在全局的高度上，为每一步决策提供有效的策略，使得最终局中人的收益最大，遗憾最小。其实不难发现，投资者在市场中时时刻刻都面临着非完美信息、扩展式博弈：我们不可能知道市场中所有的信息，需要利用有限已知的信息做出一系列投资决策。如果将博弈的局中人看成是市场上所有的投资者，将所有投资者的集体行为抽象成市场指数的走势，那么如何在博弈中战胜市场，获得满意的收益呢？虚拟遗憾最小化恰好能够为我们挖掘策略提供有效的思路。
资本市场瞬息万变，资产价格上涨时，有人会后悔没有提早入市，而资产价格下跌时，又有人遗憾未能及时平仓。将虚拟遗憾最小化应用在量化择时中，给出预测的多空信号，将“遗憾”最小化，或者说将收益最大化，就是我们要做的事情。
当投资者和市场指数进行“博弈”时， 市场的动作序列h可以通过指数的历史数据反应。以日为时间单位，我们站在当前的时点，需要根据市场的动作序列h做出决策：做多、做空或者平仓，当前的时点就是决策点。我们通过虚拟遗憾最小化算法，给出对当前时点之后一天的预测——股价上涨概率和下跌概率，这两个值对应我们在之后一天执行做多动作和做空动作的概率。
虚拟遗憾最小化是一种迭代更新策略的方法，在交易日T，我们需要预测交易日T 1股价上涨和下跌的概率。在交易日T收盘后，决策点Ht的虚拟价值为：
上式中PT-PT-1是交易日T，T-1的收盘价之差；虚拟价值v(hT)其实就是交易日T执行策略sigmaT的平均效用值。交易日T收盘后，投资者对没有执行做多憾值是：
而动作序列hTlong的虚拟价值v(hTlong)，可以看做是执行做多动作的收益PT-PT-1。将T之前所有交易日做多动作的虚拟遗憾值求和，得到T时刻的做多的累计虚拟遗憾值RT(long):
累计虚拟遗憾值是对某一动作序列下某个决策“后悔”的总体反应，但是就像人类会对很久之前的事情发生遗忘，越久远的虚拟遗憾值的时效性就越差。为此，可以引入“遗忘系数” k（00.5,Gate2<0.5）。当sigma(long)上突破Gate1时，给出做多信号1，直到有一天sigma(long)小于0.5，给出平仓信号0；当sigma(long)下突破Gate2时，给出做空信号-1，直到有一天sigma(long)大于0.5，给出平仓信号0。阈值的设定可以减少噪声的影响，提高信号的稳定性。
根据策略产生择时信号的过程
沪深300指数的实证
要将预测的上涨(即执行买入动作）概率sigma(long)转换为多空信号，首先需要确定阈值 Gate1 和 Gate2 。用虚拟遗憾最小化算法求出沪深 300指数 在2005.1.5-2017.2.23之间每个交易日的sigma(long)， 通过sigma(long)对频数分布直方图的直观观察，选择Gate1=0.55， Gate2=0.45。
算法的一个参数是“遗忘系数” k(0 样本内，虚拟遗憾最小化策略在沪深300指数多空、纯多择时收益
样本外，虚拟遗憾最小化策略在沪深300指数多空、纯多择时收益
样本外，虚拟遗憾最小化策略在沪深 300 指数多空、纯做多择时结果
从择时结果来看，风险收益情况良好。可以看到该策略的择时次数较少，平均预测周期较长，适合中线择时。分析其中原因，与阈值Gate1和Gate2的取值有关：阈值的差越大，上涨和下跌概率越难突破阈值，看多信号1和看空信号-1就产生的越少。其实，预测的上涨概sigma(long)和下跌概率sigma(short)是虚拟遗憾在时间上累积的反映，当虚拟遗憾在时间上累积的动量突破阈值时，就会触发多空信号，及时提醒我们采取不同的策略以获得收益。
上证指数的实证
使用上证指数2005-1-4至2011-1-31内的数据做虚拟遗憾最小化策略的样本内优化，得到遗忘系数k=0.943,将k用于样本外（2011-2-1至2017-3-16）的预测，结果如下。
样本外，虚拟遗憾最小化策略在上证指数多空、纯多择时收益
中证500指数的实证
使用中证500指数2005-1-4至2011-1-31内的数据做虚拟遗憾最小化策略的样本内优化，得到遗忘系数k=0.942,将k用于样本外（2011-2-1至2017-3-16）的预测，结果如下。
样本外，虚拟遗憾最小化策略在中证500指数多空、纯多择时收益
众所周知，股指期货交易频率越高，策略对于交易成本的敏感性越强。自2015年9月7日股指期货交易制度改革以来，沪深300股指期货流动性大幅度下降，买卖盘挂单量减小，使得单笔交易成本成倍增加。由于中长线的交易策略单笔平均收益较大，覆盖高交易成本后，仍有可观的收益。所以接下来我们给出虚拟遗憾最小化算法在股指期货日频交易中的一个应用。
沪深300指数作为沪深300股指期货的标的，它的变化会立即在沪深300股指期货当中得到反应，二者有很强的相关性。我们将之前沪深300股指的多空信号应用在hs300股指期货的交易中，给出零交易费用、万二交易费用和千一交易费用下的收益情况，结果如下。
虚拟遗憾最小化策略用于IF低频交易的累积收益率
基本上是15年带动的。效果不是很好。
点宽精品课程推荐
本周值得读的文章
点宽为西安工程大学提供金融科技实践培训服务
点宽金融科技实验室预研课题新进展
点宽×湖南人文科技学院：开展金融科技发展重点与展望培训，助力金融科技人才培养
