Sequential Decision Making under uncertain

Sequential Decision Making

序列决策制定可以被归纳为为下面的交互式闭环过程：

目标：选择能够最大化未来全部收益期望的动作(actions)。

这可能不一直都是好的标准，但这是大多数强化学习所关注的。但现在也有一些人对distribution honorable强化学习和其他方面有兴趣

• 可能需要平衡即时收益和长期回报
• 可能需要策略化的行为以取得高回报(你可能需要牺牲初始阶段的高奖励以取得更好的长期奖励)

更进一步地：

在每一个时间步t:

• Agent 采取一个action$a_t$
• World 更新执行$a_t$后的状态，返回观察$o_t$和奖励$r_t$
• Agent 接收观察$o_t$和奖励$r_t$

我们可以定义一个history $h_t=(a_1,o_1,r_1,...,a_t,o_t,r_t)$

Agent基于history选择action。

State是假定去确定下一步发生什么的信息：

• 或者说State是history的一个函数：$s_t=f(h_t)$

World State

• World State(为了和State作区分，是world的真实状态，agent有自己独有的状态空间)被用于确定world如何产生下一个观察和奖励
• World State通常对agent来说是不可见的或者未知的
• 即使会包含一些agent不需要的信息

Agent State

• 被agent用于制定决策如何行动
• 总的来说是一个历史的函数$s_t=f(h_t)$
• 可以包含诸如算法状态的元信息(执行了多少计算步骤，等)或决策过程(一轮里还有多少决策需要制定)

Markov Assumption

information state：充足的history的统计数据。
State $s_t$是马尔科夫的当且仅当：
$$p(s_{t+1}|s_t,a_t)=p(s_{t+1}|h_t,a_t)$$
为了对未来做出预测，只需要知道Enviroment的当前状态，即给定现在时未来对过去是独立的。

Why is Markov Assumption Polular ？

• Markov Assumption可以一直被满足
  • 只要把state设定成history它就是马尔科夫的：$s_t=h_t$
• 在实践中通常假定最近的观察是充足的history统计数据：$s_t=o_t$
• State representation 对以下有影响：
  • 计算复杂度
  • 需要的数据量
  • 最终结果的性能

Full Observability / Markov Decision Process(MDP)

如果我们假定Environment的观察等于world的state:$s_t=o_t$，那么agent就是以马尔科夫决策过程(MDP)来建模world的。

Partial Observability / Partially Observable Markov Decision Process(POMDP)

• Agent的state和world的state是不同的(partially)
• Agent自己构建自己的state，e.g
  • 使用history $s_t=h_t$，或者使用world state的belief(信念)， 或者使用RNN

Types of Sequential Decision Process: Bandits

• Bandits(老虎机)：action对下一个观察没有影响
• 没有延期的奖励。

Bandits是一种简单的马尔科夫决策过程。

Types of Sequential Decision Process: MDPs and POMDPs

对MDP和POMDP来说：

• actions会影响未来的观察
• 可能需要奖励分配(Credit assignment)和策略化action

Types of Sequential Decision Process: How does the world changes

• Deterministic(确定性):给定一个history和action，只会产生一个观察(obsercation)和奖励(reward)
  • 在机器人和控制论里是常见假设
• Stochastic(随机性): 给定一个history和action，可能会有多个潜在的观察(obsercation)和奖励(reward)
  • 针对顾客，患者，难以建模的领域来说是常见假设