Shaping Advice in Deep Reinforcement Learning

An MDP [41] is a tuple $(S,A,\mathbb{T},\rho_{0},R)$. $S$ is the set of states, $A$ the set of actions, $\mathbb{T}:S\times A\times S\rightarrow[0,1]$ encodes $\mathbb{P}(s_{t+1}|s_{t},a_{t})$, the probability of transition to $s_{t+1}$, given current state $s_{t}$ and action $a_{t}$. $\rho_{0}$ is a probability distribution over the initial states. $R:S\times A\rightarrow\mathbb{R}$ denotes the reward that the agent receives when transitioning from $s_{t}$ while taking action $a_{t}$. In this paper, $R<\infty$.

The goal for an RL agent [1] is to learn a policy $\pi$, in order to maximize $J:=\mathbb{E}_{\tau\sim\pi}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})]$. Here, $\gamma$ is a discounting factor, and the expectation is taken over the trajectory $\tau=(s_{0},a_{0},r_{0},s_{1},\dots)$ induced by policy $\pi$. If $\pi:S\rightarrow A$, the policy is deterministic. On the other hand, a randomized policy returns a probability distribution over the set of actions, and is denoted $\pi:S\times A\rightarrow[0,1]$.

The value of a state-action pair $(s,a)$ following policy $\pi$ is represented by the Q-function, written $Q^{\pi}(s,a)=\mathbb{E}_{\tau\sim\pi}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})|s_{0}=s,a_{0}=a]$. The Q-function allows us to calculate the state value $V^{\pi}(s)=\mathbb{E}_{a\sim\pi}[Q^{\pi}(s,a)]$. The advantage of a particular action $a$, over other actions at a state $s$ is defined by $A^{\pi}(s,a):=Q^{\pi}(s,a)-V^{\pi}(s)$.

A stochastic game with $n$ players is a tuple $\mathcal{G}=(S,A^{1},\dots,A^{n},\mathbb{T},R^{1},\dots,R^{n},O^{1},\dots,O^{n},\rho_{0},\gamma)$. $S$ is the set of states, $A^{i}$ is the action set of player $i$, $\mathbb{T}:S\times A^{1}\times\dots\times A^{n}\times S\rightarrow[0,1]$ encodes $\mathbb{P}(s_{t+1}|s_{t},a^{1}_{t},\dots,a^{n}_{t})$, the probability of transition to state $s_{t+1}$ from $s_{t}$, given the respective player actions. $R^{i}:S\times A^{1}\times\dots\times A^{n}\rightarrow\mathbb{R}$ is the reward obtained by agent $i$ when transiting from $s_{t}$ while each player takes action $a^{i}_{t}$. $O^{i}$ is the set of observations for agent $i$. At every state, each agent receives an observation correlated with the state: $o^{i}:S\rightarrow O^{i}$. $\rho_{0}$ is a distribution over the initial states, and $\gamma\in[0,1]$ is a discounting factor.

A policy for agent $i$ is a distribution over actions, defined by $\pi^{i}:O^{i}\times A^{i}\rightarrow[0,1]$. Let $\bm{\pi}:=\{\pi^{1},\dots,\pi^{n}\}$ and $s:=(s^{1},\dots,s^{n})$. Following [17], in the simplest case, $s^{i}=o^{i}$ for each agent $i$, and we use this for the remainder of the paper. Additional information about states of agents can be included since we compute centralized value functions. Let $V_{i}^{\bm{\pi}}(s)=V_{i}(s,\pi^{1},\dots,\pi^{n}):=\mathbb{E}_{\bm{\pi}}[\sum_{t}\gamma^{t}R^{i}_{t}|s_{0}=s,\bm{\pi}]$ and $Q_{i}^{\bm{\pi}}(s,a^{1},\dots,a^{n}):=R^{i}+\gamma\mathbb{E}_{s^{\prime}}[V_{i}^{\bm{\pi}}(s^{\prime})]$ where $V_{i}^{\bm{\pi}}(s)=\mathbb{E}_{\{a^{i}\sim\pi^{i}\}_{i=1}^{n}}[Q_{i}^{\bm{\pi}}(s,a^{1},\dots,a^{n})]$.

Reward shaping methods augment the environment reward $R$ with an additional reward $F\in\mathbb{R}$, $F<\infty$. This changes the structure of the original MDP $M(=(S,A,\mathbb{T},\rho_{0},R))$ to $M^{\prime}=(S,A,\mathbb{T},\rho_{0},R+F)$. The goal is to choose $F$ so that an optimal policy for $M^{\prime}$, $\pi^{*}_{M^{\prime}}$, is also optimal for the original MDP $M$. Potential-based reward shaping (PBRS) schemes were shown to be able to preserve the optimality of deterministic policies in [13]. PBRS was used in model-based RL in [20], in episodic RL in [42], and was extended to planning in partially observable domains in [43]. These works focused on the finite-horizon case. In comparison, we consider the infinite horizon, discounted cost setting.

The additional reward $F$ in PBRS is defined as a difference of potentials, $\phi(\cdot)$. Specifically, $F(s_{t},a_{t},s_{t+1}):=\gamma\phi(s_{t+1})-\phi(s_{t})$. Then, the Q-function, $Q^{*}_{M}(s,a)$, of the optimal greedy policy for $M$ and the optimal Q-function $Q^{*}_{M^{\prime}}(s,a)$ for $M^{\prime}$ are related by: $Q^{*}_{M^{\prime}}(s,a)=Q^{*}_{M}(s,a)-\phi(s)$. Therefore, the optimal greedy policy is not changed [13, 44], since:

The authors of [45] augmented $\phi(s)$ to include action $a$ as an argument and termed this potential-based advice (PBA). They defined two forms of PBA, look-ahead PBA and look-back PBA, respectively defined by:

For the look-ahead PBA scheme, the state-action value function for $M$ following policy $\pi$ is given by:

The optimal greedy policy for $M$ can be recovered from the optimal state-action value function for $M^{\prime}$ using the fact [45]:

The optimal greedy policy for $M$ using look-back PBA can be recovered similarly.

In the multi-agent case, the shaping advice for an agent at each time is a function of observations and actions of all agents. The shaping advice is augmented to the environment reward during training, and can take one of two forms, look-ahead and look-back, respectively given by:

We will denote by $\mathcal{G}^{\prime}$ the $n$ player stochastic game that is identical to $\mathcal{G}$, but with rewards $R^{\prime i}:=R^{i}+F^{i}$ for each $i$.

When the value of the potential function is identical for all actions in a particular state, we will term this uniform advice. On the other hand, when the value of the potential function depends on the action taken in a state, we will term this nonuniform advice. We will explicitly distinguish between uniform and nonuniform variants of shaping advice in the single and multi-agent settings subsequently.

The shaping advice is a heuristic that uses knowledge of the environment and task, along with information available to the agent [46]. For example, in the particle world tasks that we study, each agent has access to positions of other agents and of landmarks, relative to itself. This is used to design shaping advice for individual agents at each time step.

In this paper, we develop a framework for incorporating shaping advice in RL environments with continuous action spaces. Moreover, in the multi-agent case, different from prior works that emphasize learning joint policies for agents, we learn decentralized policies for each agent.

The following result shows that SAS-Uniform preserves optimality even when the optimal policy is stochastic.

Although SAS-Uniform preserves optimality of policies in several settings, it suffers from the drawback of being unable to encode richer information, such as desired relations between states and actions. The authors of [45] proposed potential-based nonuniform advice, a scheme that augmented the potential function by including actions as an argument together with states. In this part, we show that when using SAS-NonUniform, recovering the optimal policy can be difficult if the optimal policy is stochastic. To overcome this barrier, we propose a novel way to impart prior information about the environment in order to use SAS-NonUniform to learn a stochastic policy.

To integrate SAS-NonUniform with policy gradient-based techniques, we turn to temporal difference (TD) methods. TD methods update estimates of the accumulated return based in part on other learned estimates, before the end of an episode. A popular TD-based policy gradient method is the actor-critic framework [1]. In this setup, after performing action $a_{t}$ at step $t$, the accumulated return $G(s_{t},a_{t})$ is estimated by $Q_{M}(s_{t},a_{t})$ which, in turn, is estimated by $r_{t}+\gamma V_{M}(s_{t+1})$. It should be noted that the estimates are unbiased.

When the reward is augmented with look-ahead SAS-NonUniform, the accumulated return is changed to $Q_{M^{\prime}}(s_{t},a_{t})$, which is estimated by $r_{t}+\gamma\phi(s_{t+1},a_{t+1})-\phi(s_{t},a_{t})+\gamma V_{M^{\prime}}(s_{t+1})$. From Eqn. (3), at steady state, $Q_{M}(s_{t},a_{t})-Q_{M^{\prime}}(s_{t},a_{t})=\phi(s_{t},a_{t})$. Intuitively, to keep policy gradient unbiased when augmented with look-ahead nonuniform advice, we can add $\phi(s_{t},a_{t})$ at each training step. In other words, we can use $r_{t}+\gamma\phi(s_{t+1},a_{t+1})+\gamma V_{M^{\prime}}(s_{t+1})$ as the estimated return. It should be noted that before the policy reaches steady state, adding $\phi(s_{t},a_{t})$ at each time step will not cancel out the effect of nonuniform advice. This is unlike in REINFORCE, where the addition of this term negates the effect of using nonuniform advice. In the advantage actor-critic, an advantage term is used instead of the Q-function in order to reduce the variance of the estimated policy gradient. In this case also, the potential term $\phi(s_{t},a_{t})$ can be added in order to keep the policy gradient unbiased.

A procedure for augmenting the advantage actor-critic with SAS-NonUniform is presented in Algorithm 1. $\alpha^{\theta}$ and $\alpha^{\omega}$ denote learning rates for the actor and critic respectively. When applying look-ahead nonuniform advice, at training step $t$, parameter $\omega$ of the critic $V_{\omega}(s)$ is updated as follows:

where $\delta^{a}_{t}$ is the estimation error of the state value after receiving new reward $[r_{t}+\gamma\phi(s_{t+1},a_{t+1})-\phi(s_{t},a_{t})]$ at step $t$. To ensure an unbiased estimate of the policy gradient, the potential term $\phi(s_{t},a_{t})$ is added while updating $\theta$ as [20]:

A similar method can be used when learning with look-back nonuniform advice. In this case, the critic and the policy parameter are updated as follows:

In the above case, the potential term need not be added to ensure an unbiased estimate. Then, the policy parameter update becomes:

which is exactly the policy update of the advantage actor-critic. This is formally stated in Proposition IV.2

SAM uses a centralized critic during the training phase. Information about observations and actions of all agents is used to learn a decentralized policy for each agent. One way to do this is by using an actor-critic framework, which combines policy gradients with temporal difference (TD) techniques.

At time $t$, the joint action $(a^{1}_{t},\dots,a^{n}_{t})$ is used to estimate the accumulated return for each agent $i$ as $r^{i}_{t}+\gamma V^{i}(s_{t+1})$. This quantity is called the TD-target. Subtracting $V^{i}(s_{t})$ from the TD-target gives the TD-error, which is an unbiased estimate of the agent advantage [1]. Each actor can then be updated following a gradient based on this TD-error.

We learn a separate critic for each agent like in [17]. However, the learning process can be affected when rewards provided by the environment are sparse. SAM uses a potential-based heuristic as shaping advice that is augmented to the reward received from the environment. This resulting reward is less sparse and can be used by the agents to learn policies.

We describe how to augment shaping advice to the multi-agent policy gradient to assign credit. We use the actor-critic framework with a centralized critic and decentralized actors.

For an agent $i$, shaping advice $F^{i}$ is augmented to the environment reward $r^{i}$ at each time step. $F^{i}$ is specified by a difference of potentials (Eqn. (5) or (6)). The centralized critic allows using observations and actions of all agents to specify $F^{i}$. Using look-ahead advice, $Q$-values in the modified game $\mathcal{G}^{\prime}$ with reward $R^{i}+F^{i}$ and original game $\mathcal{G}$ with reward $R^{i}$ are related as [45]:

The accumulated return in $\mathcal{G}^{\prime}$ for agent $i$ is then estimated by $r^{i}_{t}+\gamma\phi_{i}(s_{t+1},a^{i}_{t+1},a^{-i}_{t+1})-\phi_{i}(s_{t},a^{i}_{t},a^{-i}_{t})+\gamma V^{i}(s_{t+1})$. From Eqn. (16), we can add $\phi_{i}(s_{t},a^{i}_{t},a^{-i}_{t})$ to the TD-target in $\mathcal{G}^{\prime}$ at each time $t$ to keep the policy gradient unbiased in $\mathcal{G}$.

Let the critic and actor in SAM for agent $i$ be respectively parameterized by $\omega_{i}$ and $\theta_{i}$. When the actor is updated at a slower rate than critic, the asymptotic behavior of the critic can be analyzed by keeping the actor fixed using two time-scale stochastic approximation methods [47]. For agent $i$, the TD-error at time $t$ is given by:

The update of the critic can be expressed as a first-order ordinary differential equation (ODE) in $\omega_{i}$, given by:

Under an appropriate parameterization of the value function, this ODE will converge to an asymptotically stable equilibrium, denoted $\omega_{i}(\bm{\theta})$. At this equilibrium, the TD-error for agent $i$ is $\delta_{t,\omega_{i}(\bm{\theta})}^{i}=r^{i}_{t}+F^{i}_{t}+\gamma V_{\omega_{i}(\bm{\theta})}(s_{t+1})-V_{\omega_{i}(\bm{\theta})}(s_{t})$.

The update of the actor can then be determined by solving a first order ODE in $\theta_{i}$. With look-ahead advice, a term corresponding to the shaping advice at time $t$ will have to be added to ensure an unbiased policy gradient (Eqn. (16)). This ODE can be written as:

A potential term will not have to be added to ensure an unbiased policy gradient when utilizing look-back advice. This insight follows from Proposition 3 in [20] since we consider decentralized policies.

In this part, we present a proof of the convergence of the actor and critic parameters when learning with shaping advice. We also demonstrate that convergence of policy gradients and values when using SAM implies convergence of these quantities in the absence of SAM. This will guarantee that policies learned in the modified stochastic game $\mathcal{G}^{\prime}$ will be locally optimal in the original game $\mathcal{G}$.

For agent $i$, the update dynamics of the critic can be expressed by the ODE in Eqn. (18). Assuming parameterization of $V(s)$ over a linear family, this ODE will converge to an asymptotically stable equilibrium [47]. The actor update is then given by the ODE in Eqn. (19). The parameters associated with the critics are assumed to be updated on a faster timescale than those of the actors. Then, the behaviors of the actor and critic can be analyzed separately using two timescale stochastic approximation techniques [47].

We first state a useful result from [48].

Let $\{\mathcal{F}^{\omega}_{t}\}$ be the filtration where $\mathcal{F}^{\omega}_{t}:=\sigma(s_{\tau},$ $r^{1}_{\tau},\dots,r^{n}_{\tau},\omega_{1_{\tau}},\dots,\omega_{n_{\tau}}:\tau\leq t)$ is an increasing $\sigma-$algebra generated by iterates of $\omega_{i}$ up to time $t$. We first analyze behavior of the critic when parameters of the actor are fixed.

We can now analyze the behavior of the actor, assuming that the critic parameters have converged to an asymptotically stable equilibrium. With $\omega_{i}(\bm{\theta})$ a limit point of the critic update, let $\delta_{t,\omega_{i}(\bm{\theta})}^{i}=r^{i}_{t}+F^{i}_{t}+\gamma V_{\omega_{i}(\bm{\theta})}(s_{t+1})-V_{\omega_{i}(\bm{\theta})}(s_{t})$. When using look-ahead or look-back advice, define $\tilde{\delta}^{i}_{t,\omega_{i}(\bm{\theta})}$ as: