論文 Better Exploration with Optimistic Actor-Critic (2019)

# Source
* [Arxiv](https://arxiv.org/abs/1910.12807)
* [Microsoft Research Blog](https://www.microsoft.com/en-us/research/blog/optimistic-actor-critic-avoids-the-pitfalls-of-greedy-exploration-in-reinforcement-learning/)

# Introduction
### Target Problem
* Current RL methods have difficulty achieving sample efficiency, and one of the main cause is due to exploration redundancy.

Current modern actor-critic methods uses an approximate lower bound to estimate the critic, as the consequence for underestimating the true critic value is smaller than overestimating it.  They also employ the actor to both derive the best guess of the optimal action, as well as for exploration (sampling from the policy probabilities).  However, greedily maximizing the lower bound is both inefficient and inaccurate, due to two phenomenons; **pessimistic underexploration** and **directional uninformedness**.

### Pessimistic Underexploration
In the figure below, where $Q^\pi$ is the true critic and $Q_{LB}$ is the lower bound, the exploration would be severely limited once the policy reaches from $\pi_{past}$ to $\pi_{current}$, as that is the the location of lower bound maximum.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/81ee9f6e-ac4f-9919-819d-3a02a009c2fe.png)
Obviously, we can not simply use the upper bound as a simple replacement, as the same scenario will occur for overestimation.

### Directional Uninformedness
For efficiency reasons, most actor-critic models for continuous action spaces use Gaussian policies.  This means that actions in opposite directions from the mean are sampled with equal probability.  However, if the policy had moved from $\pi_{past}$ to $\pi_{current}$ like above, sampling from the right-hand side of $\pi_{current}$ would be mostly unfruitful, as we already have sufficient samples from that direction.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/c1f0d6f6-2e4c-5f35-a769-fc091e3cceec.png)

# Optimistic Actor Critic (OAC)
To combat the deficiencies of quaint exploration method, a new actor-critic algorithm, Optimistic Actor Critic (OAC), has been proposed.  OAC introduces an extra off-policy exploration policy which focuses on maximizing the upper bound of the critic, leading to more efficient learning.

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/c91bc2a7-a9bc-1d94-e4e7-7d8e873182c1.png)

While off-policy Reinforcement Learning is known to be prone to instability when combined with function approximation (known as deadly triad), OAC achieves stability by enforcing a KL constraint between the exploration policy and the target policy.

## Implementation
### Critic
Two networks (same structure but with different initialization weights), $\hat{Q}^1_{LB}$ and $\hat{Q}^2_{LB}$ are used for approximating lower confidence bound of the Q-function.  There is an additional set of target networks ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/5b704abe-f885-e0a2-834b-cab6ed833598.png) and ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/0f1f5e52-9558-036b-9eef-d26fe32e16a3.png) used to track $\hat{Q}_{LB}$.  These two target networks are updated softly depending on a constant $\tau$.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/a0a7b15e-1de2-2269-78b6-708eb4f36d6a.png)

### Actor
The actor (**target policy** $\pi_T$) is updated using the **reparametrised policy gradient** method, where a re-parametrisation function $f$ has the same probability density $f_\theta(s,\epsilon)$ as $\pi_T(a|s)$.  The gradient of the objective function $J$ is then:
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/9790625f-08e8-f464-a08d-25e604e78e0d.png)
where $\epsilon$ is a random variable sampled from a standard multivariate Gaussian $N(0,I)$.  Note that the target policy update equation uses a lower confidence bound of the critic in order to mitigate overestimation and achieve stability.

An additional **entropy** term $\triangledown_\theta H(\pi(．,s))$ is added to provide regularization and encourage exploration (adds more cost to actions with higher probability).  Since the Shannon entropy $\displaystyle H(x) = \sum_{x} p(x)\log p(x)$ for continuous random variable can be written as $H(x) = -$$\int_{x} p(x)\log p(x) dx$, equation (3) become:
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/d92e755b-fc38-951b-f870-2b8d5cd00079.png)
Through approximation using Monte-Carlo estimates, we arrive with an update equation for $\pi_T$:
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/c5468784-965b-9e10-9961-8094c482ceec.png)

### Getting the Upper Bound
1. Get an **epistemic uncertainty estimate** $\sigma_Q$ of the true state-action value function $Q$ by using bootstraps of the critic.  The mean and standard deviation are defined as:  
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/cba0fab4-3d1d-daae-1c18-5d3afa2f978b.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/541de895-33c9-2eb4-c8e2-e51d49b5c6b2.png)

2. Use $\mu_Q$ and $\sigma_Q$ to get the upper bound  $\hat{Q}_ {UB}$.
$\hat{Q}_ {UB}$ $= \mu_ Q(s, a) + \beta_ {UB}\sigma_ Q(s, a)$.
where $\beta _{UB}$ is a constant controlling level of optimism.

3. Derive the **linear approximation** $\bar{Q}_ {UB}$ of $\hat{Q}_ {UB}$ by using Taylor's theorem.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/ebf0fb18-eaa2-8034-0c2e-99946913ffb9.png)
where $\mu_T$ is the mean of $\pi_T$.

### Exploration Policy
The **exploration policy** $\pi_E = N(\mu_E, \Sigma_E)$ tries to maximize $\bar{Q}_ {UB}$.  It is computed from scratch everytime an exploration action is performed, and only used when sampling exploration actions.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/f21d4a37-b330-eea6-126e-da22fd544176.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/8b9ef780-4d82-0b37-7b45-a6d41019200f.png)
The KL constraint is important as it prevents taking catastrophically bad actions that are too far from $\pi_T$, as well as ensuring $\bar{Q}_ {UB}$ approximation is accurate, due to limitation of the Taylor's theorem (the assumption only holds in a small region near $\mu_T$).

Exploration actions can then be sampled from the constructed $\pi_E$.

### OAC Algorithm
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/8d0ba5b0-a38f-b725-78c5-c1d64ea29cea.png)

# Result
### Other SOTA Algorithm Comparison
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/37a4ec1b-2d4a-fef0-07e5-b3781d51951c.png)

### Bootstrapped Uncertainty Estimate Usefulness
$\hat{Q}_{UB}$ in (9) is replaced with $\hat{Q} _{LB}$ from (1) to investigate the effectiveness of the uncertainty estimate.  While Figure 4 shows improvement in the Humanoid task, in reality the benefit is very little to non-existent for other tasks.  Due to the computational cheapness for obtaining the upper bound, it has remained as a part of the algorithm.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/6198dd1f-7f76-2dfb-2e9d-843cebe3e913.png)

### KL constraint sensitivity
In (9), the term $\delta$ is a constant that controls the maximum allowed KL divergence between exploration policy and target policy.  It can be seen from the figure below that there exist a board range of $\delta$ that can lead to good performance.
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264921/de9d421a-e5f6-a7eb-4eb8-9e585c1c3549.png)
*Error bars indicate 90% confidence interval

# Conclusion
Despite what is written in the introduction, the experiment results contradicts the importance of pessimistic underexploration on exploration.  This leads to the deduction that the improvements made by OAC is entirely contributed to the exploration being directionally informed.

That been said, the increased sample efficiency is still evident, and perhaps could be extended to other RL algorithms, or perhaps parameter optimization.