Back to home

<Bandit Algorithms for Website Optimization>

<Bandit Algorithms for Website Optimization>

Introduction

这是一本关于如何更好的做A/B Test的书。
围绕短期利益和长期收益做的决策。

Two Characters: Exploration and Exploitation 两个人物:探索,利用

针对一个购物站是否需要换LOGO展开的故事。 科学家的观点是需要足够的测试,A/B test,Group A/B test ,最后才能充分的相信足够好,才进行改进。 商人的观点是那些只是为了知识而去了解(She wants to have knowledge for knowledge’s sake and never thinks about the costs of her experiments.),网站主本身是一个商人,一切活动均要保证网站存活,也就需要考虑到做事情的更本利益,从眼前出发,显然不做更换才是最好的策略。 最后出现一个研究者来调和。

Why Use Multiarmed Bandit Algorithms? 为什么使用多老虎机算法?

Multiarmed Bandit Algorithms : http://en.wikipedia.org/wiki/Multi-armed_bandit

衡量措施:

  • Traffic 增加的流量总量
  • Conversions 转换率,成为注册用户(原文repeat customers
  • Sales 销售率,增加的销售量
  • CTR's 点击率,广告

至于为什么需要Multiarmed Bandit Algorithms,对于传统的A/B Test,一般按照如下方式进行:

  • 一个纯粹短期的探索,分配均等的用户群A和B
  • 一个纯粹长期的利用,只让所有用户使用成功的版本,从来不尝试其他次等版本

为什么这可能是一个失败的策略?

  • 直接隔离探索和利用,你可能能够平滑的转换他们
  • 在纯粹探索阶段,这浪费资源在次等选择为了收集尽可能多的数据。但是你没有必要采用那些明显有缺陷的选择

Bandit Algorithms 为上面的建议提供了解决方案。

The epsilon-Greedy Algorithm ε贪婪算法

对于一个网站打算换LOGO,方案1是换绿色,方案2是换红色,当然也可以不换。

1662475342b0af7895a497198eec0e4c.png

如上图,ε贪婪算法很简单,就是抛硬币,如果正面朝上,那么就执行Explore,否则就Exploit 。对于Explore 可能存在多种情况的,那么就再抛一次,直到最后选出结果为止。

问题描述

什么是 Arm ?
角子机,也称老虎机。

什么是奖励?
既定评定措施的增长。

什么是Bandit问题?

  • 有N台复杂的机器,供我们抽取
  • 每次抽取的奖励并不可靠,所以我们才会赌博。有可能1%的机会收获1个单位奖励,也有可能是3%的机会,奖励往往伴随着风险
  • 不仅抽取存在风险,我们也不知道每台老虎机的获奖概率,我们将会通过实际的抽取去计算这些概率。
  • 我们只能找出已经抽取过的机器的奖励,会遗失那些我们没有抽取的。就像生活,你只能从你走过的路吸取教训。
  • 每次实验都不会是最好的决策,因为从理论上,我们总能抽取一个更好的(arm)。

在我看来,就是前途无限凶险,但是有宝藏,我们就是要尽可能的运用已知进行有限度的探索。不能停止脚步,也不能梭哈。

ε贪婪算法实现

定义一个EpsilonGreedy类,它有如下属性:

  • epsilon 抽取概率,[0,1]之间
  • conts 一个整形向量,长度为我们要抽取的老虎机数量,每一项则代表对该下标位置的老虎机抽取多少次
  • values 一个浮点向量,每个老虎机我们已得到的收益是多少

Python 版的代码风格不忍直视,不要在__init__方法调用return
下面就是全部实现:

import random

def ind_max(x):
  m = max(x)
  return x.index(m)

class EpsilonGreedy():
  def __init__(self, epsilon, counts, values):
    self.epsilon = epsilon
    self.counts = counts
    self.values = values
    return

  def initialize(self, n_arms):
    self.counts = [0 for col in range(n_arms)]
    self.values = [0.0 for col in range(n_arms)]
    return

  def select_arm(self):
    if random.random() > self.epsilon:
      return ind_max(self.values)
    else:
      return random.randrange(len(self.values))

  def update(self, chosen_arm, reward):
    self.counts[chosen_arm] = self.counts[chosen_arm] + 1
    n = self.counts[chosen_arm]

    value = self.values[chosen_arm]
    new_value = ((n - 1) / float(n)) * value + (1 / float(n)) * reward
    self.values[chosen_arm] = new_value
    return

值得注意的是,update方法的实现,主要是为了在有了一定“经验”的老虎机上,对其后来的奖励越来越不敏感。从而达到经可能的使用他的平均奖励。(This weighting is important, because it means that single observations mean less and less to the algorithm when we already have a lot of experience with any specific option. The specific weighting we’ve chosen is designed to insure that the estimated value is exactly equal to the average of the rewards we’ve gotten from each arm.)
我个人的看法是这条动态调整的曲线很好的保证了奖励对于预估的影响,想想这条曲线的积分会是一个什么样子。

TODO