Exploration and Exploitation —— 探索与利用

作者@ weanl
创建于 2018-12-22T14:30:00
参考链接：

1. 介绍

1.1 探索与利用间的困境

  • Online decision-making involves a fundamental choice:
    Exploitation Make the best decision given current information
    Exploration Gather more information
  • The best long-term strategy may involve short-term sacrifices
  • Gather enough information to make the best overall decisions

1.2 生活中栗子

  • Restaurant Selection
    Exploitation Go to your favorite restaurant
    Exploration Try a new restaurant
  • Online Banner Advertisements
    Exploitation Show the most successful advert
    Exploration Show a different advert
  • Oil Drilling
    Exploitation Drill at the best known location
    Exploration Drill at a new location
  • Game Playing
    Exploitation Play the move you believe is best
    Exploration Play an experiment move

1.3 伍种策略规则

  • Naive Exploration
    Add noise to greedy policy (e.g. \epsilon-greedy)
  • Optimistic Initialization
    Assume the best until proven otherwise
  • Optimism in the Face of Uncertainty

2. 引入多臂老虎机 (The Multi-Armed Bandit)

拉斯维加斯的一排老虎机

维基百科解释如下：
  这个名字来自于想象一个赌徒在一排老虎机（有时被称为“单臂匪徒”），他们必须决定要玩哪些机器，玩每台机器多少次以及按顺序播放它们，以及是否继续使用当前的机器或尝试不同的机器。在该问题中，每台机器从特定于该机器的概率分布中提供随机奖励。赌徒的目标是通过一系列杠杆拉动最大化获得的奖励总和。[3] [4]赌徒在每次试验中面临的关键权衡是在“利用”具有最高预期收益的机器和“探索”以获得关于其他机器的预期收益的更多信息之间。

2.1 最大化cumulative reward && 最小化 total regret

  • 动作空间和奖赏分布
      在t时刻，Agent做出动作\alpha_t \in \cal A， Environment依据未知分布\cal R^{\alpha}(r)=\mathbb P[r|\alpha]产生对应的奖赏值r_t \sim \cal R^{\alpha_t}=\mathbb P[r| \alpha_t]。动作空间和奖赏分布 可以记为二元组\langle \cal A, \cal R \rangle，产生的具体观测记为 \langle \alpha_t, r_t \rangle。
  • 最大化cumulative reward
    max \sum_{\tau=1}^{t}{r_\tau}

且听下回分解

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • rljs
    rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,499评论 0赞 10
  • 2003-2014考研真题
    **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 10,132评论 0赞 23
  • 端午喝酒
    昊哥说他只想做两件事，一是探索消费新边疆，二是完善现有系统。我觉得这两件事都很厉害。昊哥总结的很到位，很有想...
    十二班的xiaohua阅读 227评论 0赞 0
  • 肯定法
    1.俊琦，你一个人坐车从东莞过来学习。真是一个独立的男子汉啦，过马路还提醒我要看车，真是一个贴心的暖男，真的长大了...
    肖馨肖馨阅读 187评论 0赞 1
  • 孩子遇事儿态度
    案例呈现 今天上完课稳妈跟我提出意见。孩子每次都依照规矩进行排队。但是有些孩子都会自己直接插入队伍中，导致稳稳会不...
    文文的花期阅读 177评论 0赞 1