Passage below is what I wrote about year ago, when I was drilling at problems on learning in games.

经过归纳,发现看过的文章,根据player掌握的信息不同,有大致三种estimation utility的方法:

  1. Reinforcemment Learning: 参与者只能观察到自己的utility值,不清楚其解析式,也对对手的选择一无所知。因此,参与者通过尝试、只观察统计自己选择某个策略时的期望收益,然后根据对收益的统计概率来选择以后的策略。参与者犹如面对一个blackbox,因为它对博弈对手并不关心。另外,由于观察结果的随机性,这里面存在exploration和exploition的tradeoff。这就是所谓的RL。
    相关文章:
    2012[J]Reinforcement Learning for Repeated Power Control Game in Cognitive Radio Networks.pdf

  2. Bennis的这篇文章中提出了解决Explore vs Exploit tradeoff的方法,并且能让双方的混合战略收敛到一个均衡,称做LE.
  3. 迭代调整:参与者知道自己的utility解析式和对方行动的history(比如上次行动),不知道下一步的行动。此时,参与者依据博弈对方上次的选择,作为对方的下一次博弈策略,并基于此,利用BR找到自己的最优反应策略。双方均如此进行一个bargain的过程。这就把博弈问题变成了一个two-sided optimization。当双方都达到ai=BR(a-i) 为不动点时,此算法收敛。此算法对utility函数的的要求较高,一般要求双方的utility函数都是单调并且coupled decision的过程(比如supermodular Game)。在上述情况下,它能保证收敛到均衡点。IWF算法就是这样的two-side opt的应用。
    文章:(IWF)
  4. Fictitious Play(FP):参与者知道自己的utility解析式和对方行动的历史,但不知道对方下一步的选择。因此,参与者根据对手历史数据,假设对方选择它最“喜欢”选择的策略(这个策略可能是基于其博弈历史频率的混合战略,也可以是它曾经选择最多的那个纯战略),然后来估算自己选择某策略时候的期望收益。同上,由于样本有限,而且对对方的策略空间也了解有限。这个估计会有差异。但可以根据RG过程,动态调整empirical data,最后收敛到均衡解。这一过程,就是大名鼎鼎的ficticious play
    例文:
  5. Regret Matching: 参与者知道自己的utility和对方行动的历史。根据对方行动的历史,参与者计算出自己当前时刻各个策略的regret。并根据此regret赋予其下一步选择各策略的概率(混合策略),来进行行动。可以证明,当所有的参与者都选择regret matching策略时,博弈基本上都会收敛到CE。同样,此算法也依据empirical data。对信息的透明性要求较高。
  6. Stackelberg Game:假设参与者完全了解对手的utility函数及其反应策略。并能推测自己选择某种策略时,对方将选择的策略(其实就是掌握对手的BR)(比如囚徒困境、Stackleberg Game的Leader或者库诺特均衡的求解过程)。因此,只要参与者结合了自身BR,就将博弈问题转化为单方面优化问题。参与者只需要最联立BR方程组,求出交点即能找到NE。但此算法对信息的获知程度要求很高。

例文:2009[J]A new perspective on multi-user power control games in interference channels.pdf

Advertisements