# Zero Order

> [Episodic exploration for deep deterministic policies: An application to starcraft micromanagement tasks](https://arxiv.org/abs/1609.02993)

我们将实时战略游戏“星际争霸”中的场景视为强化学习算法的新基准。我们提出微观管理任务，即军队成员在战斗中的短期，低级别控制问题。从强化学习的角度来看，这些场景具有挑战性，因为状态-动作空间非常大，并且因为状态-动作评估函数没有明显的特征表示。我们描述了用深度神经网络控制器从游戏引擎给出的原始状态特性中解决微观管理问题的方法。此外，我们还提出了一种启发式强化学习算法，该算法结合了策略空间的直接探索和反向传播。这种算法允许使用确定性策略收集学习轨迹，这似乎比greedy探索更有效。实验表明，利用该算法，我们成功地学习了15个智能体组成的军队场景中的非平凡策略，在这些场景中，问题学习和强化都在进行斗争。

## 方法

### The MDP for greedy inference

一种解决联合推断命令的复杂性的方法是在每个步骤中执行贪婪推理:在每个状态下，单元一个一个地选择一个命令，知道之前由其他单元执行的命令。学习贪婪策略可以归结为在另一个MDP中学习策略，每个状态的操作更少，但是指数级的状态更多，其中附加的状态对应于贪心退单的中间步骤。这种减少以前是在Maes等人的结构化预测中提出的，他证明了在这个新MDP的最优政策与在原始MDP的最优政策具有相同的累积回报。

定义与贪婪推理关联的MDP(以下称为greedyMDP)的一种自然方法是，将贪婪策略的原子操作集定义为命令尚未确定的单元的所有可能(unit, command)对。这将导致一个关于单位数量的二次复杂度的推论，这是不可取的。

另一种可能性是首先选择一个单元，然后是一个应用于该单元的命令，它使用2 | s |步骤进行状态算法。 由于在确定所有命令后由环境同时执​​行命令，因此累积奖励不依赖于我们选择单元的顺序。 更进一步，我们可以让贪婪的MDP中的环境选择下一个单元，例如，在剩余单元中随机统一选择。于是状态集可以定义为：

![](/files/-Lbr7u5AJsk5WvKS0ucT)

其中s为输入状态，a为动作（由c、a组成），u为单位，c为单位执行的命令

状态转移概率为：

![](/files/-Lbr7xvVOpuw-RHEhzWx)

最后，使用与上述相同的符号，表示算法的中间步骤的状态之间的奖励是0，并且最后一个单元接收奖励：

![](/files/-Lbr8-t52hCeSmZfjPTf)

### Normalized cumulative rewards

在微观管理的情况中，一个自然的奖励信号是两种状态下造成的伤害和发生的伤害之间的差异。每一集的累计奖励是所造成的总伤害减去该集所遭受的总伤害。然而，这个数量的大小在很大程度上取决于在这个状态下的单位数量(包括我们的单位和敌人的单位)，这个数量会随着时间的推移而显著减少。如果没有对当前状态下的单位数量进行适当的规范化，那么学习将被人为地偏向于在剧集开始时的大量直接奖励。

我们提出了一种简单的方法，在每个状态的基础上标准化即时奖励，假设一个比例因子 $$z(s)$$ 对学习者可用，它可以是简单的单位数量。

![](/files/-Lbr90EvJpNj1BRBpzfW)

将其应用于Bellman方程(1)，得到

![](/files/-Lbr9GbVp4vOCS1NBuTN)

### Raw state information and featurization

对于每个单位（盟友或敌人），从游戏引擎给出的原始状态描述中提取以下属性：

1. 单位属性：单位类型，地图上的坐标（pos），剩余的生命点数（hp），盾牌，对应于单位未受到攻击时可以恢复的额外生命值，最后是武器冷却时间（cd） ，数字框架等待再次造成损害）。 另外一个flag用于区分我们的单位和敌方单位。
2. 描述当前由单元执行的命令的两个属性。 首先，目标属性，如果不是空的，则是当前攻击中的敌方单位的标识符。 该标识符是由游戏引擎任意归因的整数，并且不传达任何语义。 我们不直接在模型中对此标识符进行编码，而是仅使用（目标）单元的位置（如下面我们在距离特征中所述）。
3. 第二个属性，target\_pos给出标位置的地图上的坐标（如果单位当前正在移动的期望目的地，或者后者的位置不是空的）。 这些领域可用于盟友和敌方单位; 从这里我们推断出当前单位当前执行的当前命令cur\_cmd

### Deep Neural Network model

Cross featurization and pooling

用embedding层和几层ELU非线性交叉特征

Scoring with respect to action type

然后把交叉好的特征和动作类型连接，输出预测分数

### Combining backpropagation and a zero-order gradientestimates

现在，我们提出了在离散动作空间中探索确定性策略的算法，该算法基于由深度神经网络参数化的策略。该算法可以看作是一种启发式算法。我们的策略可以表示为：

![](/files/-LbrEtfUdyXy9bJybsZt)

为了在一集中以一致的方式探索策略空间，我们在单位球面上均匀地采样一个向量 $$u$$ ，并运行策略 $$\pi\_{w}+\delta u, \theta$$ ，其中 $$δ> 0$$ 是一个超参数。除了在政策空间中实施本地随机搜索之外，随机化的动机来自随机无梯度优化。梯度可以表示为：

![](/files/-LbrFTuuIMHgToduA5wy)

算法可以表示为

![](/files/-LbrExo1UIncuceS0-fH)

## 实验

![](/files/-Lbr5WeKJyTylxNNiQ1b)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hujian.gitbook.io/deep-reinforcement-learning/fang-fa/ji-shi-zhan-lve-you-xi/zero-order.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.