\section{Introduction}

A large body of reinforcement learning (RL) algorithms, based on approximate dynamic programming (ADP)~\citep{bertsekas1996neuro,scherrer2015approximate}, operate in two steps: A greedy step, where the algorithm learns a policy that maximizes a $Q$-function, and an evaluation step, that (partially) updates the $Q$-values towards the $Q$-values of the policy. A common improvement to these techniques is to use regularization, that prevents the new updated policy from being too different from the previous one, or from a fixed ``prior'' policy. For example, Kullback-Leibler (KL) regularization keeps the policy close to the previous iterate~\citep{vieillard2020leverage}, while entropy regularization keeps the policy close to the uniform one~\citep{haarnoja2018soft}. Entropy regularization, often used in this context~\citep{ziebart2010modeling}, modifies both the greedy step and the evaluation step so that the policy jointly maximizes its expected return and its entropy. In this framework, the solution to the policy optimization step is simply a softmax of the $Q$-values over the actions. In small discrete action spaces, the softmax can be computed exactly: one only needs to define a \textit{critic} algorithm, with a single loss that optimizes a $Q$-function. However, in large multi-dimensional --~or even continuous~-- action spaces, one needs to estimate it. This estimation is usually done by adding an \emph{actor} loss, that optimizes a policy to fit this softmax. It results in an \textit{actor-critic} algorithm, with two losses that are optimized simultaneously \citep{haarnoja2018soft}. This additional optimization step introduces supplementary errors to the ones already created by the approximation in the evaluation step. 

\looseness=-1
To remove these extraneous approximations, we introduce the  Implicit $Q$-Functions (IQ) algorithm, that deviates from classic actor-critics, as it optimizes a policy and a value in a single loss. The core idea is to implicitly represent the $Q$-function as the sum of a value function and a log-policy. This representation ensures that the policy is an \emph{exact} softmax of the $Q$-value, \emph{despite the use of any approximation scheme}. We use this to design a practical model-free deep RL algorithm  that optimizes with a single loss a policy network and a value network, built on this implicit representation of a $Q$-value. To better understand it, we abstract this algorithm to an ADP scheme, IQ-DP, and use this point of view to provide a detailed theoretical analysis. It relies on a key observation, that shows an equivalence between IQ-DP and a specific form of regularized Value Iteration (VI). This equivalence explains the role of the components of IQ: namely, IQ performs entropy and KL regularization. It also allows us to derive strong performance bounds for IQ-DP. In particular, we show that the errors made when following IQ-DP are compensated along iterations.

Parametrizing the $Q$-value as a sum of a log-policy and a value is reminiscent of the dueling architecture~\citep{wang2016dueling}, that factorizes the $Q$-value as the sum of an advantage and a value. In fact, we show that it is a limiting case of IQ in a discrete actions setting. 
This link highlights the role of the policy in IQ, which calls for a discussion on the necessary parametrization of the policy. 

Finally, we empirically validate IQ. We evaluate our method on several classic continuous control benchmarks: locomotion tasks from Openai Gym~\citep{brockman2016openai}, and hand manipulation tasks from the Adroit environment~\citep{rajeswaran2017learning}. On these environments, IQ reaches performances competitive with state-of-the-art actor critic methods. %



\section{Implicit $Q$-value parametrization}
\begin{wrapfigure}{r}{0.41\textwidth}
\vspace{-25pt}
\centering
  \includegraphics[width=.4\textwidth]{figures/IQ_schema.pdf}
\vspace{-10pt}
  \caption{view of the IQ parametrization.}
\label{fig:view}
\end{wrapfigure}
\label{sec:IQ}
We consider the standard Reinforcement Learning (RL) setting, formalized as a Markov Decision Process (MDP). An MDP is a tuple $\{\mathcal{S},\mathcal{A},P,r,\gamma\}$. $\mathcal{S}$ and $\mathcal{A}$ are the finite state and action spaces\footnote{We restrict to finite spaces for the sake of analysis, but our approach applies to continuous spaces.}, $\gamma\in[0,1)$ is the discount factor and $r:{\mathcal{S}\times\mathcal{A}}\rightarrow [-R_{max}, R_{max}]$ is the bounded reward function. Write $\Delta_X$ the simplex over the finite set $X$. The dynamics of an MDP are defined by a Markovian transition kernel $P\in\Delta_{\mathcal{S}}^{\mathcal{S}\times\mathcal{A}}$, where $P(s'|s,a)$ is the probability of transitioning to state $s'$ after taking action $a$ in $s$. An RL agent acts through a stochastic policy $\pi\in\Delta_\mathcal{A}^\mathcal{S}$, a mapping from states to distribution over actions. 
The quality of a policy is quantified by the value function, $V_\pi(s) = \mathbb{E}_\pi[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) | s_0=s]$. The $Q$-function is a useful extension, which notably allows choosing a (soft)-greedy action in a model-free setting, $Q_\pi(s,a) = r(s,a) + \mathbb{E}_{s' | s,a}[V_\pi(s')]$. An optimal policy is one that achieve the highest expected return, $\pi_* = \argmax_\pi V_\pi$.

\looseness=-1
A classic way to design practical algorithms beyond the tabular setting is to adopt the Actor-Critic perspective. In this framework, an RL agent parametrizes a policy $\pi_\theta$ and a $Q$-value $Q_\psi$ with function approximation, usually through the use of neural networks, and aims at estimating an optimal policy. The policy and the $Q$-function are then updated by minimizing two losses: the actor loss corresponds to the greedy step, and the  critic loss to the evaluation step. The weights of the policy and  $Q$-value networks are regularly frozen into \emph{target} weights $\bar{\psi}$ and $\bar{\theta}$. With entropy regularization, the greedy step amounts to finding the policy that maximizes $\mathbb{E}_{s \sim \mathcal{S}, a \sim \pi_\theta}[Q_{\bar\psi}(s,a) + \tau\ln\pi_\theta(a|s)]$ (maximize the $Q$-value with stochastic enough policy). The solution to this problem is simply 
$\pi_\theta(\cdot|s) = \operatorname*{softmax}({Q_{\bar{\psi}}(s,\cdot)}/{\tau}), \label{eq:softmax}$
which is the result of the greedy step of regularized Value Iteration (VI)~\citep{geist2019theory} and, for example, how the optimization step of Soft Actor-Critic \citep[SAC]{haarnoja2018soft} is built. In a setting where the action space is discrete and small, it amounts to a simple softmax computation. However, on more complex action spaces (continuous, and/or with a higher number of dimensions: as a reference, the Humanoid-v2 environment from Openai Gym~\citep{brockman2016openai} has an action space of dimension $17$), it becomes prohibitive to use the exact solution. In this case, the common practice is to resort to a approximation with a parametric distribution model. In many actor critic algorithms (SAC, TD3\citep{fujimoto2018addressing},~...), the policy is modelled as a Gaussian distribution over actions. It introduces approximation errors, resulting from the partial optimization process of the critic, and inductive bias, as a Gaussian policy cannot represent an arbitrary softmax distribution. We now turn to the description of our core contribution: the Implicit $Q$-value (IQ) algorithm, introduced to mitigate this discrepancy.

IQ implicitly parametrizes a $Q$-value via an explicit parametrization of a policy and a value, as visualized in Fig.~\ref{fig:view}. Precisely, from a policy network $\pi_\theta$ and a value network $V_\phi$, we define our implicit $Q$-value as
\begin{equation}
\label{eq:IQ-param}
    Q_{\theta, \phi}(s,a) = \tau\ln\pi_\theta(a|s) + V_\phi(s).
\end{equation}
Since $\pi_\theta$ is constrained to be a distribution over the actions, we have by construction that $\pi_\theta(a|s) = \operatorname*{softmax}(Q_{\theta,\phi}/\tau)$, the solution of the regularized greedy step (see Appx.~\ref{subappx:about} for a detailed proof). Hence, the consequence of using such a parametrization is that the greedy step is performed exactly, even in the function approximation regime. Compared to the classic actor-critic setting, it thus gets rid of the errors created by the actor. Note that calling $V_\phi$ a value makes sense, since following the same reasoning we have that $V_\phi(s) = \tau\ln\sum_{a'}\exp (Q_{\theta, \phi}(s,a')/\tau)$, a soft version of the value. With this parametrization in mind, one could derive a deep RL algorithm from any value-based loss using entropy regularization.  We conserve the fixed-point approach of the standard actor-critic framework, $\theta$ and $\phi$ are regularly copied to $\bar{\theta}$ and $\bar{\phi}$, and we design an off-policy algorithm, working on a replay buffer of transitions $(s_t, a_t, r_t, s_{st+1})$ collected during training. Consider two hyperparameters, $\tau\in(0, \infty)$ and $\alpha\in(0,1)$ that we will show in Sec.~\ref{sec:analysis} control two forms of regularization.

The policy and value are optimized jointly by minimizing the loss
\begin{equation}
\label{eq:IQ:loss}%
    \mathcal{L}_{\text{IQ}}(\theta,\phi) = \hat{\mathbb{E}}\left[\left(r_t + \alpha\tau\ln\pi_{\bar{\theta}}(a_t|s_t) + \gamma V_{\bar{\phi}}(s_{t+1}) - \tau\ln\pi_\theta(a_t|s_t) - V_\phi(s_t)\right)^2\right],
\end{equation}
\looseness=-1
where $\hat{\mathbb{E}}$ denote the empirical expected value over a dataset of transitions. IQ consists then in a single loss that optimizes jointly a policy and a value. This brings a notable remark on the role of $Q$-functions in RL. Indeed, $Q$-learning was introduced by~\citet{watkins1992q} -- among other reasons -- to make greediness possible without a model (using a value only, one needs to maximize it over all possible successive states, which requires knowing the transition model), and consequently derive practical, model-free RL algorithms. Here however, IQ illustrates how, with the help of regularization, one can derive a model-free algorithm that does not rely on an explicit $Q$-value.



\section{Analysis}
\label{sec:analysis}
In this section, we explain the workings of the IQ algorithm defined by Eq.~\eqref{eq:IQ:loss} and detail the influence of its hyperparameters. We abstract IQ into an ADP framework, and show that, from that perspective, it is equivalent to a Mirror Descent VI (MD-VI) scheme~\citep{geist2019theory}, with both entropy and KL regularization. Let us first introduce some useful notations. We make use of the actions partial dot-product notation: for $u,v\in\mathbb{R^{\mathcal{S}\times\mathcal{A}}}$, we define $\langle u, v\rangle = \big(\sum_{a\in\mathcal{A}}u(s,a)v(s,a)\big)_s \in \mathbb{R}^\mathcal{S}$. For any $V\in\mathbb{R}^\mathcal{S}$, we have for any $(s,a)\in\mathcal{S}\times\mathcal{A}$ $PV(s,a) = \sum_{s'}P(s'|s,a)V(s')$. We will define regularized algorithms, using the entropy of a policy, $H(\pi) = -\langle \pi, \ln\pi\rangle$, and the KL divergence between two policies, $\kl{\pi}{\mu}=\langle\pi, \ln\pi - \ln\mu\rangle$. The $Q$-value of a policy is the unique fixed point of its Bellman operator $T_\pi$ defined for any $Q\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ as $T_\pi Q = r + \gamma P\langle \pi,Q \rangle$. We denote $Q_*=Q_{\pi_*}$ the optimal $Q$-value (the $Q$-value of the optimal policy). When the MDP is entropy-regularized with a temperature $\tau$, a policy  $\pi$ admits a \textit{regularized} $Q$-value $Q_\pi^\tau$, the fixed point of the regularized bellman operator $T_\pi^\tau Q = r + \gamma P\langle\pi, Q - \tau\ln\pi\rangle$. A regularized MDP admits an optimal \textit{regularized} policy $\pi_*^{\tau}$ and a unique optimal \textit{regularized} $Q$-value $Q_*^\tau$~\citep{geist2019theory}.


\subsection{Ideal case}
First, let us look at the ideal case, \emph{i.e.} when $\mathcal{L}_{\text{IQ}}$ is exactly minimized at each iteration (tabular representation, dataset covering the whole state-action space, expectation rather than sampling for transitions). In this context, IQ can be understood as a Dynamic Programming (DP) scheme that iterates on a policy $\pi_{k+1}$ and a value $V_k$. They are respectively equivalent to the target networks $\pi_{\bar\theta}$ and $V_{\bar\phi}$, while the next iterate $(\pi_{k+2}, V_{k+1})$ matches the solution $(\pi_\theta, V_\phi)$ of the optimization problem in Eq.~\eqref{eq:IQ:loss}. We call the scheme IQ-DP$(\alpha, \tau)$ and one iteration is defined by choosing $(\pi_{k+2}, V_{k+1})$ such that the squared term in Eq.~\eqref{eq:IQ:loss} is $0$, that is
\begin{equation}
\label{eq:IQ-DP}
    \tau\ln \pi_{k+2} + V_{k+1} = r + \alpha\tau\ln\pi_{k+1} + \gamma P V_k. 
\end{equation}
This equation is well-defined, due to the underlying constraint that $\pi_{k+2} \in \Delta^\states_\mathcal{A}$ (the policy must be a distribution over actions), that is $\sum_{a\in\mathcal{A}}\pi(a|s) = 1$ for all $s\in\mathcal{S}$.  The basis for our discussion will be the equivalence of this scheme to a version of regularized VI. Indeed, we have the following result, proved in Appendix~\ref{appx:adp}.
\begin{theorem}
\label{thm:equivalence}
For any $k\geq1$, let $(\pi_{k+2}, V_{k+1})$ be the solution of IQ-DP$(\alpha, \tau)$ at step $k$. We have that
\begin{equation}
\begin{cases}
    \pi_{k+2} = \argmax\langle\pi, r + \gamma P V_k\rangle + (1 - \alpha)\tau \mathcal{H}(\pi) - \alpha\tau \kl{\pi}{\pi_{k+1}} \\
    V_{k+1} = \langle\pi_{k+2}, r + \gamma P V_k\rangle + (1 - \alpha)\tau \mathcal{H}(\pi_{k+2}) - \alpha\tau \kl{\pi_{k+2}}{\pi_{k+1}}
\end{cases} 
\end{equation}
so IQ-DP($\alpha, \tau$) produces the same sequence of policies as a value-based version of Mirror Descent VI, MD-VI$(\alpha\tau, (1-\alpha)\tau)$~\citep{vieillard2020leverage}.
\end{theorem}

\paragraph{Discussion.} The previous results sheds a first light on the nature of the IQ method. Essentially, IQ-DP is a parametrization of a VI scheme regularized with both  entropy and KL divergence, MD-VI$(\alpha\tau, (1-\alpha)\tau)$. This first highlights the role of the hyperparameters, as its shows the interaction between the two forms of regularization. The value of $\alpha$ balances between those two: with $\alpha=0$, IQ-DP reduces to a classic VI regularized with entropy; with $\alpha=1$ only the KL regularization will be taken into account. The value of $\tau$ then controls the amplitude of this regularization. In particular, in the limit $\alpha=0, \tau \rightarrow 0$, we recover the standard VI algorithm. This results also justifies the soundness of IQ-DP. Indeed, this MD-VI scheme is known to converge to $\pi_*^{(1-\alpha)\tau}$ the optimal policy of the regularized MDP~\citep[Thm.~2]{vieillard2020leverage} and this results readily applies to IQ\footnote{\citet{vieillard2020leverage} show this for $Q$-functions, but it can straightforwardly be extended to value functions.}. Another consequence is that it links IQ to  Advantage Learning (AL)~\citep{bellemare2016increasing}. Indeed, AL is a limiting case of MD-VI when $\alpha>0$ and $\tau\rightarrow0$ \citep{vieillard2020munchausen}. Therefore, IQ also generalizes AL, and the $\alpha$ parameter can be interpreted as the advantage coefficient. Finally, a key observation is that IQ performs KL regularization implicitly, the way it was introduced by Munchausen RL~\citep{vieillard2020munchausen}, by augmenting the reward with the $\alpha\tau\ln\pi_{k+1}$ term (Eq.~\eqref{eq:IQ-DP}). This observation will have implications discussed next. %


\subsection{Error propagation result}
\label{subsec:error}
Now, we are interested in understanding how errors introduced by the function approximation used propagate along iterations. At iteration $k$ of IQ, denote $\pi_{k+1}$ and $V_k$  the target networks. In the approximate setting, we do not solve Eq.~\eqref{eq:IQ-DP}, but instead, we minimize $\mathcal{L}(\theta, \phi)$ with stochastic gradient descent. This means that $\pi_{k+2}$ and $V_{k+1}$ are the result of this optimization, and thus the next target networks. The optimization process introduces errors, that come from many sources: partial optimization, function approximation (policy and value are approximated with neural networks), finite data, etc. We study the impact of these errors on the distance between the optimal $Q$-value of the MDP and the regularized $Q$-value of the current policy used by IQ, $Q_{\pi_{k+1}}^{(1-\alpha)\tau}$. We insist right away that $Q_{\pi_{k+1}}^{(1-\alpha)\tau}$ is not the learned, implicit $Q$-value, but the actual $Q$-value of the policy computed by IQ in the regularized MDP. We have the following result concerning the error propagation.
\begin{theorem} \label{thm:error}
Write $\pi_{k+1}$ and $V_k$ the $k^{th}$ update of respectively the target policy and value networks. Consider the error at step $k$, $\epsilon_k\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, as the difference between the ideal and the actual updates of IQ. Formally, we define the error as, for all $k \geq 1$,
\begin{equation}
    \epsilon_k = \tau\ln\pi_{k+2} + V_{k+1} - (r + \alpha\tau\ln\pi_{k+1} + \gamma P V_k),
\end{equation}
and the moving average of the errors as
\begin{equation}
    E_k = (1 - \alpha) \sum_{j=1}^{k}\alpha^{k-j}\epsilon_j. 
\end{equation}
We have the following results for two different cases depending on the value of $\alpha$. Note that when $\alpha<1$, we bound the distance to regularized optimal $Q$-value.
\begin{enumerate}
    \item General case: $0 < \alpha <1$ and $\tau> 0$, entropy and KL regularization together:
\begin{equation}
      \|Q_*^{(1-\alpha)\tau} - Q_{\pi_k}^{(1-\alpha)\tau}\|_{\infty}\leq \frac{2}{(1 - \gamma)^2}\left((1-\gamma)\sum_{j=1}^k \gamma^{k-j} \Vert E_j \Vert_\infty \right) + o\left(\frac{1}{k}\right).
\end{equation}
     \item Specific case $\alpha=1$, $\tau > 0$, use of KL regularization alone:
\begin{equation}
     \|Q_* - Q_{\pi_k}\|_{\infty}\leq 
    \frac{2}{1-\gamma} \left\|\frac{1}{k}\sum_{j=1}^k \epsilon_j\right\|_\infty
    + O\left(\frac{1}{k}\right). %
\end{equation}
\end{enumerate}
\end{theorem}
\begin{proof}[Sketch of proof.]
The full proof is provided in Appendix~\ref{appx:error}. We build upon the connection we established between IQ-DP and a VI scheme regularized by both KL and entropy in Thm.~\ref{thm:equivalence}. By injecting the proposed representation into the classic MD-VI scheme, we can build upon the analysis of~\citet[Thm.~1 and~2]{vieillard2020leverage} to provide these results.
\end{proof}

\paragraph{Impact of KL regularization.} The KL regularization term, and specifically in the MD-VI framework, is discussed extensively by~\citet{vieillard2020leverage}, and we refer to them for in-depth analysis of the subject. We recall here the main interests of KL regularization, as illustrated by the bounds of Thm~\ref{thm:error}. In the second case, where it is the clearest (only KL is used), we observe a beneficial property of KL regularization: Averaging of errors. Indeed, in a classic non-regularized VI scheme
~\citep{scherrer2015approximate}, the error $ \|Q_* - Q_{\pi_{\theta}}\|$ would depend on a moving average of the norms of the errors $(1-\gamma)\sum_{j=1}^{k}\gamma^{k-j}\Vert\epsilon_k\Vert_\infty$, while with the KL it depends on the norm of the average of the errors $(1/k)\Vert\sum_{j=1}^{k}\epsilon_k\Vert$. In a simplified case where the errors would be i.i.d. and zero mean, this would allow convergence of approximate MD-VI, but not of approximate VI. In the case $\alpha<1$, where we introduce entropy regularization, the impact is less obvious, but we still transform a sum of norm of errors into a sum of moving average of errors, which can help by reducing the underlying variance.

\paragraph{Link to Munchausen RL.} As stated in the sketched proof, Thm.~\ref{thm:error} is a consequence of~\citep[Thm.~1 and~2]{vieillard2020leverage}. A crucial limitation of this work is that the analysis only applies when no errors are made in the greedy step. This is possible in a relatively simple setting, with tabular representation, or with a linear parametrization of the $Q$-function. However, in the general case with function approximation, exactly solving the optimization problem regularized by KL is not immediately possible: the solution of the greedy step of MD-VI$(\alpha\tau, (1-\alpha)\tau)$ is $\pi_{k+2} \propto \exp(Q_{k+1}/\tau)\pi_k^\alpha$ (where $Q_{k+1} = r + \gamma P V_k$), so computing it exactly would require remembering every $\pi_j$ during the procedure, which is not feasible in practice. A workaround to this issue was introduced by~\citet{vieillard2020munchausen} as Munchausen RL: the idea is to augment the reward by the log-policy, to implicitly define a KL regularization term, while reducing the greedy step to a softmax. As mentioned before, in small discrete action spaces, this allows to compute the greedy step exactly, but it is not the case in multidimensional or continuous action spaces, and thus Munchausen RL loses its interest in such domains. With IQ, we utilize the Munchausen idea to implicitly define the KL regularization; but with our parametrization, the exactness of the greedy step holds even for complex action spaces: recall that the parametrization defined in Eq.~\eqref{eq:IQ-param} enforces that the policy is a softmax of the (implicit) $Q$-value. Thus, IQ can be seen as an extension of Munchausen RL to multidimensional and continuous action spaces. 



\subsection{Link to the dueling architecture}

Dueling Networks (DN) were introduced as a variation of the seminal Deep Q-Networks (DQN, \citet{mnih2015human}), and has been empirically proven to be efficient (for example by~\citet{hessel2018rainbow}). The idea is to represent the $Q$-value as the sum of a value and an advantage. In this setting, we work with a notion of advantage defined over $Q$-functions (as opposed to defining the advantage as a function of a policy). For any $Q\in\mathbb{R^{\mathcal{S}\times\mathcal{A}}}$, its advantage $A_Q$ is  defined $A_Q(s,a) = Q(s,a) - \max_{a'\in\mathcal{A}}Q(s,a')$. The advantage encodes a sub-optimality constraint: it has negative values and its maximum over actions (the action maximizing the $Q$-value) is $0$. \citet{wang2016dueling} propose to learn a $Q$-value by defining and advantage network $F_\Theta$ and a value network $V_\Phi$, which in turn define a $Q$-value $Q_{\Theta, \Phi}$ as
\begin{equation}
\label{eq:advantage}
    Q_{\Theta, \Phi}(s,a) =  \underbrace{F_\Theta(s,a) - \max_{a'\in\mathcal{A}}F_\Theta(s,a')}_{\text{advantage}} + V_\Phi(s).
\end{equation}
Subtracting the maximum over the actions ensures that the advantage network indeed represents an advantage. Note that dueling DQN was designed for discrete action settings, where computing the maximum over actions is not an issue.

In IQ, we need a policy network that represents a distribution over the actions. There are several practical ways to represent the policy, that are discussed in Sec~\ref{sec:practical}. For the sake of simplicity, let us for now assume that we are in a mono-dimensional discrete action space, and that we use a common scaled softmax representation. Specifically, our policy is represented by a neural network (eg. fully connected) $F_\theta$, that maps state-action pairs to logits $F_\theta(s,a)$. The policy is then defined as $\pi_\theta(\cdot|s) = \operatorname*{softmax}(F_\theta(s,\cdot)/\tau)$. Directly from the definition of the softmax, we observe that $\tau\ln\pi_\theta(a|s) = F_\theta(s,a) - \tau\ln\sum_{a'\in\mathcal{A}}\exp(F_\theta(s,a')/\tau)$. The second term is a classic scaled logsumexp over the actions, a soft version of the maximum: when $\tau\rightarrow 0$, we have that $\tau\ln\sum_a'\exp(F(s,a')/\tau) \rightarrow \max_{a'}F(s,a')$. Within the IQ parametrization, we have
\begin{equation}
\label{eq:soft-advantage}
    Q_{\theta,\phi} = \underbrace{F_\theta(s,a) - \tau\ln\sum_{a'\in\mathcal{A}}\exp(F(s,a')/\tau)}_{\text{soft-advantage}} + V_\phi(s),
\end{equation}
\looseness=-1
which makes a clear link between IQ and DN. In this case (scaled softmax representation), the IQ parametrization generalizes the dueling architecture, retrieved when $\tau\rightarrow0$ (and with an additional AL term whenever $\alpha>0$, see Sec.~\ref{sec:analysis}). In practice,~\citet{wang2016dueling} use a different parametrization of the advantage, replacing the maximum by a mean, defining $Q_{\Theta, \Phi}(s,a) =  A_\Theta(s,a) - |\mathcal{A}|^{-1}\sum_{a'\in\mathcal{A}}A_\Theta(s,a') + V_\Phi(s)$. We could use a similar trick and replace the logsumexp by a mean in our policy parametrization, but in our case this did not prove to be efficient in practice.

We showed how the log-policy represents a soft version of the advantage. While this makes its role in the learning procedure clearer, it also raises questions about what sort of representation would be the most suited for optimization.

\section{Practical considerations} \label{sec:practical}
We now describe key practical issues encountered when choosing a policy representation. The main one comes from the delegation of the representation power of the algorithm to the policy network. In a standard actor-critic algorithm -- take SAC for example, where the policy is parametrized as a Gaussian distribution -- the goal of the policy is mainly to track the maximizing action of the $Q$-value. Thus, estimation errors can cause the policy to  choose sub-optimal actions, but the inductive bias caused by the Gaussian representation may not be a huge issue in practice, as long as the mean of the Gaussian policy is not too far from the maximizing action. In other words, the representation capacity of an algorithm such as SAC lies mainly in the representation capacity of its $Q$-network. 

In IQ, we have a parametrization of the policy that enforces it to be a softmax of an implicit $Q$-value. By doing this, we trade in estimation error -- our greedy step is exact by construction -- for representation power. More precisely, as the $Q$-value is not parametrized explicitly, but through the policy, the representation power of IQ is in its policy network, and a ``simple'' representation might not be enough anymore. For example, if we parameterized the policy as a Gaussian, this would amount to parametrize an advantage as a quadratic function of the action: this would drastically limit what the IQ could represent. 

\paragraph{Multicategorical policies.} To address this issue, we turn to other, richer, distribution representations. In practice, we consider a multi-categorical discrete softmax distribution. Precisely, we are in the context of a multi-dimensional action space $\mathcal{A}$ of dimension $d$, each dimension being a bounded interval. %
We discretize each dimension of the space uniformly  in $n$ values $\delta_j$, for $0\leq j\leq n-1$.
It effectively defines a discrete action space $\mathcal{A}' = \bigtimes_{j=1}^d \mathcal{A}_j$, with $\mathcal{A}_j = \{\delta_0, \hdots \delta_{n-1}\}$. A multidimensional action is a vector $a\in\mathcal{A}'$, and we denote $a^j$ the $j^{\text{th}}$ component of the action $a$. 
Assuming independence between actions conditioned on states, 
a policy $\pi_\theta$ can be factorized as the product of $d$ marginal mono-dimensional policies
$\pi_\theta(a|s) = \prod_{j=1}^d \pi^{j}_\theta(a^j|s)$.
We represent each policy as the softmax of the output of a neural network $F_\theta^j$, an thus we get the full representation
\begin{equation}
\label{eq:multicat}
    \pi_\theta(a|s) =  \prod_{j=1}^d \operatorname*{softmax}\left(F_\theta^j(\cdot|s)\right)(a^j).
\end{equation}
The  $F_\theta^j$ functions can be represented as neural networks with a shared core, which only differ in the last layer. This type of multicategorical policy can represent any distribution (with $n$ high enough) that does not encompass a dependency between the dimensions. The independence assumption is quite strong, and does not hold in general. From an advantage point of view, it assumes that the soft-advantage (\textit{i.e.} the log-policy) can be linearly decomposed along the actions. While this somehow limits the advantage representation, it is a much weaker constraint than paramterizing the advantage as a quadratic function of the action (which would be the case with a Gaussian policy). In practice, these types of multicategorical policies have been experimented~\citep{akkaya2019solving, tang2020discretizing}, and have proven to be efficient on continuous control tasks.

\looseness=-1
Even richer policy classes can be explored. To account for dependency between  dimensions, one could envision auto-regressive multicategorical representations, used for example to parametrize a $Q$-value by~\citet{metz2017discrete}. Another approach is to use richer continuous distributions, such as  normalizing flows~\citep{rezende2015variational, ward2019improving}. In this work, we restrict ourselves to the multicategorical setting, which is sufficient to get satisfying results (Sec.~\ref{subsec:results}), and we leave the other options for future work.

\section{Related work}
\paragraph{Similar parametrizations.} Other algorithms make use of a similar parametrization. First, Path Consistency Learning (PCL,~\citep{nachum2017bridging}) also parametrize the $Q$-value as a sum of a log-policy and a value. Trust-PCL~\citep{nachum2017trust}, builds on PCL by adding a trust region constraint on the policy update, similar to our KL regularization term. A key difference with IQ is that (Trust-)PCL is a residual algorithm, while IQ works around a fixed-point scheme. Shortly, Trust-PCL can be seen as a version of IQ without the target value network $V_{\bar\phi}$. These entropy-regularized residual approaches are derived from the softmax temporal  consistency principle, which allows to consider extensions to  a specific form of multi-step learning (strongly relying on the residual aspect), but they also come with drawbacks, such as introducing a bias in the optimization when the environment is stochastic~\citep{geist2016bellman}.
Second, Quinoa~\citep{degrave2019quinoa}  uses a similar loss to Trust-PCL and IQ (without reference to the former Trust-PCL), but do not propose any analysis, and is evaluated only on a few tasks.
Third, Normalized Advantage Function (NAF,~\citet{gu2016continuous}) is designed with similar principles. In NAF, a $Q$-value is parametrized as a value and and an advantage, the former being quadratic on the action. It matches the special case of IQ with a Gaussian policy, where we recover this quadratic parametrization.

\paragraph{Regularization.} Entropy and KL regularization are used by many other RL algorithms. Notably, from a dynamic programming perspective, IQ-DP(0, $\tau$) performs the same update as SAC -- an entropy regularized VI. This equivalence is however not true in the function approximation regime. Due to the empirical success of SAC and its link to IQ, it will be used as our main baseline on continuous control tasks. Other algorithms also use KL regularization, notably Maximum a posteriori Policy Optimization (MPO,~\citet{abdolmaleki2018maximum}). We refer to~\citet{vieillard2020leverage} for an exhaustive review of algorithms encompassed within the MD-VI framework.


\section{Experiments}
\looseness=-1


\paragraph{Environments and metrics.} We evaluate IQ first on the Mujoco environment from OpenAI Gym~\citep{brockman2016openai}. It consists of $5$ locomotion tasks, with action spaces ranging from $3$ (Hopper-v2) to $17$ dimensions (Humanoid-v2). We use a rather long time horizon setting, evaluating our algorithm on $20$M steps on each environments. We also provide result on the Adroit manipulation dataset~\citep{rajeswaran2017learning}, with a similar setting of $20$M environment steps. Adroit is a collection of $4$ hand manipulation tasks. This environment is often use in an offline RL setting, but here we use it only as a direct RL benchmark. Out of these $4$ tasks, we only consider $3$ of them: We could not find any working algorithm (baseline or new) on the ``relocate'' task. To summarize the performance of an algorithm, we report the baseline-normalized score along iterations: It normalizes the score so that $0\%$ corresponds to a random score, and $100\%$ to a given baseline. It is defined for one task as
$\text{score} = \frac{\text{score}_\text{algorithm} - \text{score}_\text{random}}{\text{score}_\text{baseline} - \text{score}_\text{random}}$,
where the baseline is the best version of SAC on Mujoco and Adroit after $20$M steps. We then report aggregated results, showing the mean and median of these normalized scores along the tasks. Each score is reported as the average over $20$ random seeds. For each experiment, the corresponding standard deviation is reported in~\ref{subappx:results}

\looseness=-1
\paragraph{IQ algorithms.} We implement IQ with the Acme~\citep{hoffman2020acme} codebase. It defines two deep neural networks, a policy network $\pi_\theta$ and a value network $V_\phi$. IQ interacts with the environment through $\pi_\theta$, and collect transitions that are stored in a FIFO replay buffer. At each interaction, IQ updates $\theta$ and $\phi$ by performing a step of stochastic gradient descent with  Adam~\citep{kingma2014adam} on $\mathcal{L}_{\text{IQ}}$ (Eq.~\eqref{eq:IQ:loss}). During each step, IQ updates a copy of the weights $\theta$, $\bar\theta$, with a smooth update $\bar\theta \leftarrow (1-\lambda)\bar\theta + \lambda\theta$, with $\lambda\in(0,1)$. It tracks a similar copy $\bar\phi$ of $\phi$. We keep almost all common hyperparameters (networks architecture, $\lambda$, etc.) the same as our main baseline, SAC. We only adjust the learning rate for two tasks, Humanoid and Walker, where we used a lower value: we found that IQ benefits from this, while for SAC we did not observe any improvement (we provide more details and complete results in Appx.~\ref{subappx:results}). Our value network has the same architecture as the SAC $Q$-networks except that the input size is only the state size (as it does not depend on the action). The policy network has the same architecture as the SAC policy network, and differs only by its output: IQ policy outputs a multicategorical policy (so $n\cdot d$ values, where $d$ is the dimensionality of the action space and $n$ is the number of discrete action on each dimension), while SAC policy outputs $2$ $d$-dimensional vectors (mean and diagonal covariance matrix of a Gaussian). We use $n=11$ in our experiments. IQ introduces two hyperparameters, $\alpha$ and $\tau$. We tested several values of $\tau$ between $10^{-4}$ and $1$, and selected a value per task suite: we use $\tau=0.01$ on Mujoco tasks and $\tau=0.001$ on Adroit. We tested values of $\alpha$ in $\{0., 0.1, 0.5, 0.9, 0.99 \}$. To make the distinction between the cases when $\alpha=0$ and $\alpha>0$, we denote IQ($\alpha>0$) as M-IQ, for Munchausen-IQ, since it makes use of the Munchausen regularization term. For M-IQ, we found $\alpha=0.9$ to be the best performing value, which is consistent with the findings of~\citet{vieillard2020munchausen}. We report results for non-optimal values of $\tau$ in the ablation study (Section~\ref{sec:results}).
Extended explanations are provided in Appendix~\ref{subappx:pc}.

\looseness=-1
\paragraph{Baselines.} On continuous control tasks, our main baseline is SAC, as it reaches state-of-the-art performance on Mujoco tasks. We compare to the version of SAC that uses an adaptive temperature for reference, but note that for IQ we keep a fixed temperature ($\tau$) setting. To reach its best performance, SAC either uses a specific temperature value per task, or an adaptive scheme that controls the entropy of the policy. This method could be extended to multicategorical policies, but we leave this for future work, and for IQ we use the same value of $\tau$ for all tasks of an environment ($10^{-2}$ on Gym, $10^{-3}$ on Adroit). We use SAC with the default parameters from~\citet{haarnoja2018soft2} on Gym, and a specificly tuned version of SAC on Adroit. Remarkably, SAC and IQ work with similar hyperparameter ranges on both benchmarks. We only found that using a learning rate of $3\cdot10^{-5}$ (instead of $3\cdot10^{-4}$) gave better performance on Adroit. We also compare IQ to Trust-PCL. It is the closest algorithm to IQ, with a similar parametrization. To be fair, we compare to our version of Trust-PCL, which is essentially a residual version of IQ, where the target value network $V_{\bar\phi}$ is replaced by the online one. We use Trust-PCL with a fixed temperature, and we tuned this temperature to the environment. We found that Trust-PCL reaches its best performance with significantly lower values of $\tau$ compared to IQ. In the ablation (Fig.~\ref{fig:ablation}) we used $\tau=10^{-4}$ for PCL and Trust-PCL.


\label{subsec:results}
\label{sec:results}

\paragraph{Comparison to baselines.} We report aggregated results of IQ and M-IQ on Gym in Fig.~\ref{fig:mujoco_iq} and on Adroit in Fig.~\ref{fig:adroit_iq}, and corresponding standard deviations in Appx.~\ref{subappx:results}. IQ reaches competitive performance to SAC. It is less sample efficient on Gym (SAC reaches higher performance sooner), but faster on Adroit, and IQ reaches a close final performance on both environments. These results also show the impact of the $\alpha$ parameter. Although the impact of  the Munchausen term (\textit{i.e} KL regularization) might not seem as impressive as in discrete actions, these results show that using that term is never detrimental, and can even bring a slight improvement on Gym; while it does not add any compute complexity to the algorithm. We also report scores on each individual task in Appx.~\ref{subappx:results}, along with in-depth discussion on the performance and the impact of hyperparameters.

\begin{figure}
    \centering
    \includegraphics[width=.49\linewidth]{figures/nlc_mujoco_mean_20s_full_best.pdf}
    \includegraphics[width=.49\linewidth]{figures/nlc_mujoco_median_20s_full_best.pdf}
    \caption{SAC-normalized scores on Gym. \textbf{Left}: Mean scores. \textbf{Right:} Median scores.}
    \label{fig:mujoco_iq}
    \label{fig:ablation}
\end{figure}
\begin{figure}
    \centering
   \includegraphics[width=.49\linewidth]{figures/nlc_adroit_mean_20s.pdf}
    \includegraphics[width=.49\linewidth]{figures/nlc_adroit_median_20s.pdf}
    \caption{SAC-normalized scores on Adroit. \textbf{Left}: Mean scores. \textbf{Right:} Median scores.}
    \label{fig:adroit_iq}
\end{figure}

\paragraph{Influence of the temperature.} We study the influence of the temperature on the Mujoco tasks in Fig.~\ref{fig:mujoco_temp}. We report the score of IQ for several values of $\tau$ (with $\alpha=0$ here,and with $\alpha>0$ in Appx.\ref{subappx:results}), on all environments of Mujoco. It shows that $\tau$ needs to be selected carefully: while it helps learning, too high values of $\tau$ can be detrimental to the performance, and it highlights that its optimal value might be dependant on the task. Another observation is that $\tau$ has a much stronger influence on IQ than $\alpha$. This is a key empirical difference regarding the performance of M-DQN~\citep{vieillard2020munchausen}. M-DQN shares similar $\tau$ and $\alpha$ parameters, but is specific to discrete actions. It benefits from a high value of $\alpha$: M-DQN with $\alpha=0.9$ largely outperforms M-DQN with $\alpha=0$ on the Atari benchmark. While this term still has effect in IQ on some tasks, it is empirically less useful, even though it is never detrimental; this discrepancy is yet to be understood.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{figures/mujoco_temp_0.0.pdf}
    \caption{Influence of $\tau$ on IQ with $\alpha=0$.}
    \label{fig:mujoco_temp}
\end{figure}

\looseness=-1
\paragraph{Ablation study.} We perform an ablation on important components of IQ in Fig.~\ref{fig:ablation}. \textbf{(1)} We replace the target network by its online counterpart in Eq.~\eqref{eq:IQ:loss}, which gives us Trust-PCL (and PCL is obtained by setting $\alpha=0$), a residual version of our method. IQ and M-IQ both outperform Trust-PCL and PCL on Mujoco. \textbf{(2)} We use a Gaussian parametrization of the policy instead of a multicategorical distribution. We observe on Fig.~\ref{fig:ablation} that this causes the performance to drop drastically. This empirically validates the considerations about the necessary complexity of the policy from Section~\ref{sec:practical}.

\section{Conclusion}
\looseness=-1
We introduced IQ, a parametrization of a $Q$-value that mechanically preserves the softmax relation between a policy and an implicit $Q$-function. Building on this parametrization, we derived an off-policy algorithm, that learns a policy and a value by minimizing a single loss, in a fixed-point fashion. We provided insightful analysis that justifies our parametrization and the algorithm. Specifically, IQ performs entropy and (implicit) KL regularization on the policy. While this kind of regularization had already been used and analyzed in RL, it was limited by the difficulty of estimating the softmax of $Q$-function in continuous action settings. IQ ends this limitation by avoiding any approximation in this softmax, effectively extending the analysis of this regularization. This parametrization comes at a cost: it shifts the representation capacity from the $Q$-network to the policy, which makes the use of Gaussian representation ineffective. We solved this issue by considering simple multicategorical policies, which allowed IQ to reach performance comparable to state-of-the-art methods on classic continuous control benchmarks. Yet, we envision that studying even richer policy classes may results in even better performance. In the end, this work brings together theory and practice: IQ is a theory-consistent manner of implementing an algorithm based on regularized VI in continuous actions settings.


\clearpage

\bibliographystyle{plainnat}

\subsubsection*{\bibname}}


\usepackage[utf8]{inputenc} %
\usepackage[T1]{fontenc}    %
\usepackage{hyperref}       %
\usepackage{url}            %
\usepackage{booktabs}       %
\usepackage{amsfonts}       %
\usepackage{nicefrac}       %
\usepackage{microtype}      %
\usepackage{xcolor}         %
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{dsfont}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{mathtools}
\mathtoolsset{showonlyrefs=true}
\usepackage{enumerate}
\usepackage{authblk}
\usepackage{ bbold }
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{authblk}
\usepackage{wrapfig}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem*{recall_thm1}{Theorem~\ref{thm:equivalence}}
\newtheorem*{recall_thm2}{Theorem~\ref{thm:error}}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{property}{Property}

\newcommand{\argmax}{\operatorname*{argmax}} 
\newcommand{\operatorname*{argmin}}{\operatorname*{argmin}}
\newcommand{\operatorname*{softmax}}{\operatorname*{softmax}}
\newcommand{\kl}[2]{\operatorname*{KL}(#1||#2)}
\newcommand{\lse}[1]{\operatorname*{lse}\left(#1\right)}
\newcommand{\mathbb{R}}{\mathbb{R}}
\newcommand{\mathcal{H}}{\mathcal{H}}
\newcommand{\mathcal{R}}{\mathcal{R}}
\newcommand{\mathcal{S}}{\mathcal{S}}
\newcommand{\mathcal{A}}{\mathcal{A}}
\newcommand{\Delta^\states_\mathcal{A}}{\Delta^\mathcal{S}_\mathcal{A}}
\newcommand{\mathbb{1}}{\mathbb{1}}
\newcommand{\mathbb{E}}{\mathbb{E}}
\newcommand{\mathcal{G}}{\mathcal{G}}
\newcommand{\mathbf{1}}{\mathbf{1}}
\DeclareMathOperator{\FC}{FC}
\DeclareMathOperator{\Conv}{Conv}

\newcommand{\mfg}[1]{{\color{blue}[mfg: #1]}}
\newcommand{\nino}[1]{{\color{red}[nino: #1]}}






\begin{document}



\runningauthor{Nino Vieillard, Marcin Andrychowicz,  Anton Raichuk, Olivier Pietquin, Matthieu Geist}

\twocolumn[

\aistatstitle{Implicitly Regularized RL with Implicit Q-values}

\aistatsauthor{Nino Vieillard$^{1,2}$ \And Marcin Andrychowicz$^{1}$ \And  Anton Raichuk$^{1}$}
\aistatsauthor{Olivier Pietquin$^{1}$ \And Matthieu Geist$^{1}$}

\aistatsaddress{$^{1}$Google Research, Brain Team \quad $^{2}$Universit\'e de Lorraine, CNRS, Inria, IECL, F-54000 Nancy, France}]





\begin{abstract}

The $Q$-function is a central quantity in many Reinforcement Learning (RL) algorithms for which RL agents behave following a (soft)-greedy policy w.r.t. to $Q$. It is a powerful tool that allows action selection without a model of the environment and even without explicitly modeling the policy. Yet, this scheme can only be used in discrete action tasks, with small numbers of actions, as the softmax over actions cannot be computed exactly otherwise.  More specifically, the usage of function approximation to deal with continuous action spaces in modern actor-critic architectures intrinsically prevents the exact computation of a softmax. We propose to alleviate this issue by parametrizing the $Q$-function \emph{implicitly}, as the sum of a log-policy and a value function. We use the resulting parametrization to derive a practical off-policy deep RL algorithm, suitable for large action spaces, and that enforces the softmax relation between the policy and the $Q$-value. We provide a theoretical analysis of our algorithm: from an Approximate Dynamic Programming perspective, we show its equivalence to a regularized version of value iteration, accounting for both entropy and Kullback-Leibler regularization, and that enjoys beneficial error propagation results.  We then evaluate our algorithm on classic control tasks, where its results compete with state-of-the-art methods. 


\end{abstract}


\section{INTRODUCTION}

A large body of reinforcement learning (RL) algorithms, based on approximate dynamic programming (ADP)~\citep{bertsekas1996neuro,scherrer2015approximate}, operate in two steps: a greedy step, where the algorithm learns a policy that maximizes a $Q$-value, and an evaluation step, that (partially) updates the $Q$-values towards the $Q$-values of the policy. A common improvement to these techniques is to use regularization, that prevents the new updated policy from being too different from the previous one, or from a fixed ``prior'' policy. For example, Kullback-Leibler (KL) regularization keeps the policy close to the previous iterate~\citep{vieillard2020leverage}, while entropy regularization keeps the policy close to the uniform one~\citep{haarnoja2018soft}. Entropy regularization, often used in this context~\citep{ziebart2010modeling}, modifies both the greedy step and the evaluation step so that the policy jointly maximizes its expected return and its entropy. In this framework, the solution to the policy optimization step is simply a softmax of the $Q$-values over the actions. In small discrete action spaces, the softmax can be computed exactly: one only needs to define a \textit{critic} algorithm, with a single loss that optimizes a $Q$-value. However, in large multi-dimensional --~or even continuous~-- action spaces, one needs to estimate it. This estimation is usually done by adding an \emph{actor} loss, that optimizes a policy to fit this softmax. It results in an (off-policy) \textit{actor-critic} algorithm, with two losses that are optimized simultaneously\footnote{We refer here specifically to \emph{off-policy} actor-critics, built on a value-iteration-like scheme. For on-policy actor-critics, losses are optimized sequentially, and the policy is usually fully evaluated.} \citep{degris2012off}. This additional optimization step introduces supplementary errors to the ones already created by the approximation in the evaluation step. 

\looseness=-1
To remove these extraneous approximations, we introduce the  Implicit $Q$-values (IQ) algorithm, that deviates from classic actor-critics, as it optimizes a policy and a value in a single loss. The core idea is to implicitly represent the $Q$-value as the sum of a value function and a log-policy. This representation ensures that the policy is the \emph{exact} softmax of the $Q$-value, \emph{despite the use of any approximation scheme}. We use this to design a practical model-free deep RL algorithm  that optimizes with a single loss a policy network and a value network, built on this implicit representation of a $Q$-value. To better understand it, we abstract this algorithm to an ADP scheme, IQ-DP, and use this point of view to provide a detailed theoretical analysis. It relies on a key observation, that shows an equivalence between IQ-DP and a specific form of regularized Value Iteration (VI). This equivalence explains the role of the components of IQ: namely, IQ performs entropy and KL regularization. It also allows us to derive strong performance bounds for IQ-DP. In particular, we show that the errors made when following IQ-DP are compensated along iterations.

Parametrizing the $Q$-value as a sum of a log-policy and a value is reminiscent of the dueling architecture~\citep{wang2016dueling}, that factorizes the $Q$-value as the sum of an advantage and a value. In fact, we show that it is a limiting case of IQ in a discrete actions setting. 
This link highlights the role of our policy, which calls for a discussion on its necessary parametrization. 

Finally, we empirically validate IQ. We evaluate our method on several classic continuous control benchmarks: locomotion tasks from Openai Gym~\citep{brockman2016openai}, and hand manipulation tasks from the Adroit environment~\citep{rajeswaran2017learning}. On these environments, IQ reaches performances competitive with state-of-the-art actor-critic methods. %



\section{IMPLICIT $Q$-VALUE PARAMETRIZATION}

\begin{figure}
\centering
  \includegraphics[trim={0 3cm 0cm 5.5cm},clip,width=.4\textwidth]{figures/IQ_schema.pdf}
  \caption{view of the IQ parametrization.}
\label{fig:view}
\end{figure}
\label{sec:IQ}
We consider the standard Reinforcement Learning (RL) setting, formalized as a Markov Decision Process (MDP). An MDP is a tuple $\{\mathcal{S},\mathcal{A},P,r,\gamma\}$. $\mathcal{S}$ and $\mathcal{A}$ are the finite state and action spaces\footnote{We restrict to finite spaces for the sake of analysis, but our approach applies to continuous spaces.}, $\gamma\in[0,1)$ is the discount factor and $r:{\mathcal{S}\times\mathcal{A}}\rightarrow [-R_{max}, R_{max}]$ is the bounded reward function. Write $\Delta_X$ the simplex over the finite set $X$. The dynamics of an MDP are defined by a Markovian transition kernel $P\in\Delta_{\mathcal{S}}^{\mathcal{S}\times\mathcal{A}}$, where $P(s'|s,a)$ is the probability of transitioning to state $s'$ after taking action $a$ in $s$. An RL agent acts through a stationary stochastic policy $\pi\in\Delta_\mathcal{A}^\mathcal{S}$, a mapping from states to distribution over actions. 
The quality of a policy is quantified by the value function, $V_\pi(s) = \mathbb{E}_\pi[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) | s_0=s]$. The $Q$-function is a useful extension, which notably allows choosing a (soft)-greedy action in a model-free setting, $Q_\pi(s,a) = r(s,a) + \mathbb{E}_{s' | s,a}[V_\pi(s')]$. An optimal policy is one that achieve the highest expected return, $\pi_* = \argmax_\pi V_\pi$.

\looseness=-1
A classic way to design practical algorithms beyond the tabular setting is to adopt the Actor-Critic perspective. In this framework, an RL agent parametrizes a policy $\pi_\theta$ and a $Q$-value $Q_\psi$ with function approximation, usually through the use of neural networks, and aims at estimating an optimal policy. The policy and the $Q$-function are then updated by minimizing two losses: the actor loss corresponds to the greedy step, and the  critic loss to the evaluation step. The weights of the policy and  $Q$-value networks are regularly frozen into \emph{target} weights $\bar{\psi}$ and $\bar{\theta}$. With entropy regularization, the greedy step amounts to finding the policy that maximizes $\mathbb{E}_{s \sim \mathcal{S}, a \sim \pi_\theta}[Q_{\bar\psi}(s,a) - \tau\ln\pi_\theta(a|s)]$ (maximize the $Q$-value with stochastic enough policy). The solution to this problem is simply 
$\pi_\theta(\cdot|s) = \operatorname*{softmax}({Q_{\bar{\psi}}(s,\cdot)}/{\tau}), \label{eq:softmax}$
which is the result of the greedy step of regularized Value Iteration (VI)~\citep{geist2019theory} and, for example, how the optimization step of Soft Actor-Critic \citep[SAC]{haarnoja2018soft} is built. In a setting where the action space is discrete and small, it amounts to a simple softmax computation. However, on more complex action spaces (continuous, and/or with a higher number of dimensions: as a reference, the Humanoid-v2 environment from Openai Gym~\citep{brockman2016openai} has an action space of dimension $17$), it becomes prohibitive to use the exact solution. In this case, the common practice is to resort to an approximation with a parametric distribution model. In many actor critic algorithms (SAC, MPO~\citep{abdolmaleki2018maximum},~...), the policy is modelled as a Gaussian distribution over actions. It introduces approximation errors, resulting from the partial optimization process of the critic, and inductive bias, as a Gaussian policy cannot represent an arbitrary softmax distribution. We now turn to the description of our core contribution: the Implicit $Q$-value (IQ) algorithm, introduced to mitigate this discrepancy.

IQ implicitly parametrizes a $Q$-value via an explicit parametrization of a policy and a value, as visualized in Fig.~\ref{fig:view}. Precisely, from a policy network $\pi_\theta$ and a value network $V_\phi$, we define our implicit $Q$-value as
\begin{equation}
\label{eq:IQ-param}
    Q_{\theta, \phi}(s,a) = \tau\ln\pi_\theta(a|s) + V_\phi(s).
\end{equation}
Since $\pi_\theta$ is constrained to be a distribution over the actions, we have by construction that $\pi_\theta(a|s) = \operatorname*{softmax}(Q_{\theta,\phi}/\tau)$, the solution of the regularized greedy step (see Appx.~\ref{subappx:about} for a detailed proof). Hence, the consequence of using such a parametrization is that the greedy step is performed exactly, even in the function approximation regime. Compared to the classic actor-critic setting, it thus gets rid of the errors created by the actor. Note that calling $V_\phi$ a value makes sense, since following the same reasoning we have that $V_\phi(s) = \tau\ln\sum_{a'}\exp (Q_{\theta, \phi}(s,a')/\tau)$, a soft version of the value. With this parametrization in mind, one could derive a deep RL algorithm from any value-based loss using entropy regularization.  We conserve the fixed-point approach of the standard actor-critic framework, $\theta$ and $\phi$ are regularly copied to $\bar{\theta}$ and $\bar{\phi}$, and we design an off-policy algorithm, working on a replay buffer of transitions $(s_t, a_t, r_t, s_{t+1})$ collected during training. Consider two hyperparameters, $\tau\in(0, \infty)$ and $\alpha\in(0,1)$ that we will show in Sec.~\ref{sec:analysis} control two forms of regularization.
The policy and value are optimized jointly by minimizing the loss
\begin{multline}
\label{eq:IQ:loss}%
    \mathcal{L}_{\text{IQ}}(\theta,\phi) = \hat{\mathbb{E}}\Big[\big(r_t + \alpha\tau\ln\pi_{\bar{\theta}}(a_t|s_t) + \gamma V_{\bar{\phi}}(s_{t+1}) \\
    - \tau\ln\pi_\theta(a_t|s_t) - V_\phi(s_t)\big)^2\Big],
\end{multline}
\looseness=-1
where $\hat{\mathbb{E}}$ denote the empirical expected value over a dataset of transitions. IQ consists then in a single loss that optimizes jointly a policy and a value. This brings a notable remark on the role of $Q$-functions in RL. Indeed, $Q$-learning was introduced by~\citet{watkins1992q} -- among other reasons -- to make greediness possible without a model (using a value only, one needs to maximize it over all possible successive states, which requires knowing the transition model), and consequently derive practical, model-free RL algorithms. Here however, IQ illustrates how, with the help of regularization, one can derive a model-free algorithm that does not rely on an explicit $Q$-value.



\section{ANALYSIS}
\label{sec:analysis}
In this section, we explain the workings of the IQ algorithm defined by Eq.~\eqref{eq:IQ:loss} and detail the influence of its hyperparameters. We abstract IQ into an ADP framework, and show that, from that perspective, it is equivalent to a Mirror Descent VI (MD-VI) scheme~\citep{geist2019theory}, with both entropy and KL regularization. Let us first introduce some useful notations. We make use of the actions partial dot-product notation: for $u,v\in\mathbb{R^{\mathcal{S}\times\mathcal{A}}}$, we define $\langle u, v\rangle = \big(\sum_{a\in\mathcal{A}}u(s,a)v(s,a)\big)_s \in \mathbb{R}^\mathcal{S}$. For any $V\in\mathbb{R}^\mathcal{S}$, we have for any $(s,a)\in\mathcal{S}\times\mathcal{A}$ $PV(s,a) = \sum_{s'}P(s'|s,a)V(s')$. We will define regularized algorithms, using the entropy of a policy, $\mathcal{H}(\pi) = -\langle \pi, \ln\pi\rangle$, and the KL divergence between two policies, $\kl{\pi}{\mu}=\langle\pi, \ln\pi - \ln\mu\rangle$. The $Q$-value of a policy is the unique fixed point of its Bellman operator $T_\pi$ defined for any $Q\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ as $T_\pi Q = r + \gamma P\langle \pi,Q \rangle$. We denote $Q_*=Q_{\pi_*}$ the optimal $Q$-value (the $Q$-value of the optimal policy). When the MDP is entropy-regularized with a temperature $\tau$, a policy  $\pi$ admits a \textit{regularized} $Q$-value $Q_\pi^\tau$, the fixed point of the regularized Bellman operator $T_\pi^\tau Q = r + \gamma P\langle\pi, Q - \tau\ln\pi\rangle$. A regularized MDP admits an optimal \textit{regularized} policy $\pi_*^{\tau}$ and a unique optimal \textit{regularized} $Q$-value $Q_*^\tau$~\citep{geist2019theory}.


\subsection{Ideal case}
\looseness=-1
First, let us look at the ideal case, \emph{i.e.} when $\mathcal{L}_{\text{IQ}}$ is exactly minimized at each iteration (tabular representation, dataset covering the whole state-action space, expectation rather than sampling for transitions). In this context, IQ can be understood as a Dynamic Programming (DP) scheme that iterates on a policy $\pi_{k+1}$ and a value $V_k$. They are respectively equivalent to the target networks $\pi_{\bar\theta}$ and $V_{\bar\phi}$, while the next iterate $(\pi_{k+2}, V_{k+1})$ matches the solution $(\pi_\theta, V_\phi)$ of the optimization problem in Eq.~\eqref{eq:IQ:loss}. We call the scheme IQ-DP$(\alpha, \tau)$ and one iteration is defined by choosing $(\pi_{k+2}, V_{k+1})$ such that the squared term in Eq.~\eqref{eq:IQ:loss} is $0$, %
\begin{equation}
\label{eq:IQ-DP}
    \tau\ln \pi_{k+2} + V_{k+1} = r + \alpha\tau\ln\pi_{k+1} + \gamma P V_k. 
\end{equation}
This equation is well-defined, due to the underlying constraint that $\pi_{k+2} \in \Delta^\states_\mathcal{A}$ (the policy must be a distribution over actions), that is $\sum_{a\in\mathcal{A}}\pi(a|s) = 1$ for all $s\in\mathcal{S}$.  The basis for our discussion will be the equivalence of this scheme to a version of regularized VI. Indeed, we have the following result, proved in Appendix~\ref{appx:adp}.
\begin{theorem}
\label{thm:equivalence}
For any $k\geq1$, let $(\pi_{k+2}, V_{k+1})$ be the solution of IQ-DP$(\alpha, \tau)$ at step $k$. We have that
\begin{equation}
\begin{cases}
    \pi_{k+2} = \argmax\langle\pi, r + \gamma P V_k\rangle + (1 - \alpha)\tau \mathcal{H}(\pi) \\
              \hfill - \alpha\tau \kl{\pi}{\pi_{k+1}} \\
    V_{k+1} = \langle\pi_{k+2}, r + \gamma P V_k\rangle + (1 - \alpha)\tau \mathcal{H}(\pi_{k+2}) \\
                \hfill - \alpha\tau \kl{\pi_{k+2}}{\pi_{k+1}}
\end{cases} 
\end{equation}
so IQ-DP($\alpha, \tau$) produces the same sequence of policies as a value-based version of Mirror Descent VI, MD-VI$(\alpha\tau, (1-\alpha)\tau)$~\citep{vieillard2020leverage}.
\end{theorem}

\paragraph{Discussion.} The previous results shed a first light on the nature of the IQ method. Essentially, IQ-DP is a parametrization of a VI scheme regularized with both  entropy and KL divergence, MD-VI$(\alpha\tau, (1-\alpha)\tau)$. This first highlights the role of the hyperparameters, as its shows the interaction between the two forms of regularization. The value of $\alpha$ balances between those two: with $\alpha=0$, IQ-DP reduces to a classic VI regularized with entropy; with $\alpha=1$ only the KL regularization will be taken into account. The value of $\tau$ then controls the amplitude of this regularization. In particular, in the limit $\alpha=0, \tau \rightarrow 0$, we recover the standard VI algorithm. This results also justifies the soundness of IQ-DP. Indeed, this MD-VI scheme is known to converge to $\pi_*^{(1-\alpha)\tau}$ the optimal policy of the regularized MDP~\citep[Thm.~2]{vieillard2020leverage} and this results readily applies to IQ\footnote{\citet{vieillard2020leverage} show this for $Q$-functions, but it can straightforwardly be extended to value functions.}. Another consequence is that it links IQ to  Advantage Learning (AL)~\citep{bellemare2016increasing}. Indeed, AL is a limiting case of MD-VI when $\alpha>0$ and $\tau\rightarrow0$ \citep{vieillard2020munchausen}. Therefore, IQ also generalizes AL, and the $\alpha$ parameter can be interpreted as the advantage coefficient. Finally, a key observation is that IQ performs KL regularization implicitly, the way it was introduced by Munchausen RL~\citep{vieillard2020munchausen}, by augmenting the reward with the $\alpha\tau\ln\pi_{k+1}$ term (Eq.~\eqref{eq:IQ-DP}). This observation will have implications discussed next. %


\subsection{Error propagation result}
\label{subsec:error}
Now, we are interested in understanding how errors introduced by the function approximation used propagate along iterations. At iteration $k$ of IQ, denote $\pi_{k+1}$ and $V_k$  the target networks. In the approximate setting, we do not solve Eq.~\eqref{eq:IQ-DP}, but instead, we minimize $\mathcal{L}(\theta, \phi)$ with stochastic gradient descent. This means that $\pi_{k+2}$ and $V_{k+1}$ are the result of this optimization, and thus the next target networks. The optimization process introduces errors, that come from many sources: partial optimization, function approximation (policy and value are approximated with neural networks), finite data, etc. We study the impact of these errors on the distance between the optimal $Q$-value of the MDP and the regularized $Q$-value of the current policy used by IQ, $Q_{\pi_{k+1}}^{(1-\alpha)\tau}$. We insist right away that $Q_{\pi_{k+1}}^{(1-\alpha)\tau}$ is not the learned, implicit $Q$-value, but the actual $Q$-value of the policy computed by IQ in the regularized MDP. We have the following result concerning the error propagation.
\begin{theorem} \label{thm:error}
Write $\pi_{k+1}$ and $V_k$ the $k^{th}$ update of respectively the target policy and value networks. Consider the error at step $k$, $\epsilon_k\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, as the difference between the ideal and the actual updates of IQ. Formally, we define the error as, for all $k \geq 1$,
$$
    \epsilon_k = \tau\ln\pi_{k+2} + V_{k+1} - (r + \alpha\tau\ln\pi_{k+1} + \gamma P V_k),
$$
and the moving average of the errors as
$
    E_k = (1 - \alpha) \sum_{j=1}^{k}\alpha^{k-j}\epsilon_j 
$.
We have the following results for two different cases depending on the value of $\alpha$. Note that when $\alpha<1$, we bound the distance to regularized optimal $Q$-value.
\begin{enumerate}
    \item General case: $0 < \alpha <1$ and $\tau> 0$, entropy and KL regularization together:
\begin{multline}
      \|Q_*^{(1-\alpha)\tau} - Q_{\pi_k}^{(1-\alpha)\tau}\|_{\infty} \leq\\
       \frac{2}{(1 - \gamma)^2}\left((1-\gamma)\sum_{j=1}^k \gamma^{k-j} \Vert E_j \Vert_\infty \right) + o\left(\frac{1}{k}\right).
\end{multline}
     \item Specific case $\alpha=1$, $\tau > 0$, use of KL regularization alone:
\begin{equation}
     \|Q_* - Q_{\pi_k}\|_{\infty}\leq 
    \frac{2}{1-\gamma} \left\|\frac{1}{k}\sum_{j=1}^k \epsilon_j\right\|_\infty
    + O\left(\frac{1}{k}\right). %
\end{equation}
\end{enumerate}
\end{theorem}
\begin{proof}[Sketch of proof.]
The full proof is provided in Appendix~\ref{appx:error}. We build upon the connection we established between IQ-DP and a VI scheme regularized by both KL and entropy in Thm.~\ref{thm:equivalence}. By injecting the proposed representation into the classic MD-VI scheme, we can build upon the analysis of~\citet[Thm.~1 and~2]{vieillard2020leverage} to provide these results.
\end{proof}

\paragraph{Impact of KL regularization.} The KL regularization term, and specifically in the MD-VI framework, is discussed extensively by~\citet{vieillard2020leverage}, and we refer to them for in-depth analysis of the subject. We recall here the main interests of KL regularization, as illustrated by the bounds of Thm~\ref{thm:error}. In the second case, where it is the clearest (only KL is used), we observe a beneficial property of KL regularization: Averaging of errors. Indeed, in a classic non-regularized VI scheme
~\citep{scherrer2015approximate}, the error $ \|Q_* - Q_{\pi_{\theta}}\|$ would depend on a moving average of the norms of the errors $(1-\gamma)\sum_{j=1}^{k}\gamma^{k-j}\Vert\epsilon_k\Vert_\infty$, while with the KL it depends on the norm of the average of the errors $(1/k)\Vert\sum_{j=1}^{k}\epsilon_k\Vert$. In a simplified case where the errors would be i.i.d. and zero mean, this would allow convergence of approximate MD-VI, but not of approximate VI. In the case $\alpha<1$, where we introduce entropy regularization, the impact is less obvious, but we still transform a sum of norm of errors into a sum of moving average of errors, which can help by reducing the underlying variance.

\paragraph{Link to Munchausen RL.} As stated in the sketched proof, Thm.~\ref{thm:error} is a consequence of~\citep[Thm.~1 and~2]{vieillard2020leverage}. A crucial limitation of this work is that the analysis only applies when no errors are made in the greedy step. This is possible in a relatively simple setting, with tabular representation, or with a linear parametrization of the $Q$-function. However, in the general case with function approximation, exactly solving the optimization problem regularized by KL is not immediately possible: the solution of the greedy step of MD-VI$(\alpha\tau, (1-\alpha)\tau)$ is $\pi_{k+2} \propto \exp(Q_{k+1}/\tau)\pi_k^\alpha$ (where $Q_{k+1} = r + \gamma P V_k$), so computing it exactly would require remembering every $\pi_j$ during the procedure, which is not feasible in practice. A workaround to this issue was introduced by~\citet{vieillard2020munchausen} as Munchausen RL: the idea is to augment the reward by the log-policy, to implicitly define a KL regularization term, while reducing the greedy step to a softmax. As mentioned before, in small discrete action spaces, this allows to compute the greedy step exactly, but it is not the case in multidimensional or continuous action spaces, and thus Munchausen RL loses its interest in such domains. With IQ, we utilize the Munchausen idea to implicitly define the KL regularization; but with our parametrization, the exactness of the greedy step holds even for complex action spaces: recall that the parametrization defined in Eq.~\eqref{eq:IQ-param} enforces that the policy is a softmax of the (implicit) $Q$-value. Thus, IQ can be seen as an extension of Munchausen RL to multidimensional and continuous action spaces. 



\subsection{Link to the dueling architecture}

Dueling Networks (DN) were introduced as a variation of the seminal Deep Q-Networks (DQN, \citet{mnih2015human}), and have been empirically proven to be efficient (for example by~\citet{hessel2018rainbow}). The idea is to represent the $Q$-value as the sum of a value and an advantage. In this setting, we work with a notion of advantage defined over $Q$-functions (as opposed to defining the advantage as a function of a policy). For any $Q\in\mathbb{R^{\mathcal{S}\times\mathcal{A}}}$, its advantage $A_Q$ is  defined as $A_Q(s,a) = Q(s,a) - \max_{a'\in\mathcal{A}}Q(s,a')$. The advantage encodes a sub-optimality constraint: it has negative values and its maximum over actions is $0$. \citet{wang2016dueling} propose to learn a $Q$-value by defining an advantage network $F_\Theta$ and a value network $V_\Phi$, which in turn define a $Q$-value $Q_{\Theta, \Phi}$ as
\begin{equation}
\label{eq:advantage}
    Q_{\Theta, \Phi}(s,a) =  \textcolor{BrickRed}{F_\Theta(s,a) - \max_{a'\in\mathcal{A}}F_\Theta(s,a')} + V_\Phi(s).
\end{equation}
Subtracting the maximum over the actions ensures that $F_\Theta$ indeed represents an advantage (in \textcolor{BrickRed}{red}). Note that dueling DQN was designed for discrete settings, where computing the maximum over actions is not an issue.

In IQ, we need a policy network that represents a distribution over the actions. There are several practical ways to represent the policy, discussed in Sec~\ref{sec:practical}. For the sake of simplicity, let us for now assume that we are in a mono-dimensional discrete action space, and that we use a common scaled softmax representation. Specifically, our policy is represented by a neural network (eg. fully connected) $F_\theta$, that maps state-action pairs to logits $F_\theta(s,a)$. The policy is then defined as $\pi_\theta(\cdot|s) = \operatorname*{softmax}(F_\theta(s,\cdot)/\tau)$. Directly from the definition of the softmax, we observe that $\tau\ln\pi_\theta(a|s) = F_\theta(s,a) - \tau\ln\sum_{a'\in\mathcal{A}}\exp(F_\theta(s,a')/\tau)$. The second term is a classic scaled logsumexp over the actions, a soft version of the maximum: when $\tau\rightarrow 0$, we have that $\tau\ln\sum_a'\exp(F(s,a')/\tau) \rightarrow \max_{a'}F(s,a')$. Within the IQ parametrization, we have
\begin{equation}
\label{eq:soft-advantage}
    Q_{\theta, \phi}(s,a) =  \textcolor{BrickRed}{F_\theta(s,a) - \tau\ln\sum_{a'\in\mathcal{A}}\exp\frac{F_\theta(s,a')}{\tau}} + V_\phi(s),
\end{equation}
\looseness=-1
where we highlighted in \textcolor{BrickRed}{red} the soft advantage component, analog to the advantage in Eq.~\eqref{eq:advantage}, which makes a clear link between IQ and DN. In this case (scaled softmax representation), the IQ parametrization generalizes the dueling architecture, retrieved when $\tau\rightarrow0$ (and with an additional AL term whenever $\alpha>0$, see Sec.~\ref{sec:analysis}). In practice,~\citet{wang2016dueling} use a different parametrization of the advantage, replacing the maximum by a mean, defining $Q_{\Theta, \Phi}(s,a) =  A_\Theta(s,a) - |\mathcal{A}|^{-1}\sum_{a'\in\mathcal{A}}A_\Theta(s,a') + V_\Phi(s)$. We could use a similar trick and replace the logsumexp by a mean in our policy parametrization, but in our case this did not prove to be efficient in practice.

We showed how the log-policy represents a soft advantage. While this explicits  its role in the learning procedure, it also raises questions about which representation would be the most suited for optimization.

\section{PRACTICAL CONSIDERATIONS} \label{sec:practical}
We now describe key practical issues encountered when choosing a policy representation. The main one comes from the delegation of the representation power of the algorithm to the policy network. In a standard actor-critic algorithm -- take SAC for example, where the policy is parametrized as a Gaussian distribution -- the goal of the policy is mainly to track the maximizing action of the $Q$-value. Thus, estimation errors can cause the policy to  choose sub-optimal actions, but the inductive bias caused by the Gaussian representation may not be a huge issue in practice, as long as the mean of the Gaussian policy is not too far from the maximizing action. In other words, the representation capacity of an algorithm such as SAC lies mainly in the representation capacity of its $Q$-network.  In IQ, we have a parametrization of the policy that enforces it to be a softmax of an implicit $Q$-value. By doing this, we trade in estimation error -- our greedy step is exact by construction -- for representation power. Indeed, as our $Q$-value is not parametrized explicitly, but through the policy, the representation power of IQ is in its policy network, and a ``simple'' representation might not be enough anymore. For example, if we parameterized the policy as a Gaussian, this would amount to parametrize an advantage as a quadratic function of the action: this would drastically limit what the IQ policy could represent (in terms of soft-advantage). 

\paragraph{Multicategorical policies.} To address this issue, we turn to other, richer, distribution representations. In practice, we consider a multi-categorical discrete softmax distribution. Precisely, we are in the context of a multi-dimensional action space $\mathcal{A}$ of dimension $d$, each dimension being a bounded interval. %
We discretize each dimension of the space uniformly  in $n$ values $\delta_j$, for $0\leq j\leq n-1$.
It effectively defines a discrete action space $\mathcal{A}' = \bigtimes_{j=1}^d \mathcal{A}_j$, with $\mathcal{A}_j = \{\delta_0, \hdots \delta_{n-1}\}$. A multidimensional action is a vector $a\in\mathcal{A}'$, and we denote $a^j$ the $j^{\text{th}}$ component of the action $a$. 
Assuming independence between actions conditioned on states, 
a policy $\pi_\theta$ can be factorized as the product of $d$ marginal mono-dimensional policies
$\pi_\theta(a|s) = \prod_{j=1}^d \pi^{j}_\theta(a^j|s)$.
We represent each policy as the softmax of the output of a neural network $F_\theta^j$, an thus we get the full representation
$
\label{eq:multicat}
    \pi_\theta(a|s) =  \prod_{j=1}^d \operatorname*{softmax}(F_\theta^j(\cdot|s))(a^j).
$
The  $F_\theta^j$ functions can be represented as neural networks with a shared core, which only differ in the last layer. This type of multicategorical policy can represent any distribution (with $n$ high enough) that does not encompass a dependency between the dimensions. The independence assumption is quite strong, and does not hold in general. From an advantage point of view, it assumes that the soft-advantage (\textit{i.e.} the log-policy) can be linearly decomposed along the actions. While this limits the advantage representation, it is a much weaker constraint than paramterizing the advantage as a quadratic function of the action (which would be the case with a Gaussian policy). In practice, these types of policies have been experimented~\citep{akkaya2019solving, tang2020discretizing}, and have proven to be efficient on continuous control tasks.

\looseness=-1
Even richer policy classes can be explored. To account for dependency between  dimensions, one could envision auto-regressive multicategorical representations, used for example to parametrize a $Q$-value by~\citet{metz2017discrete}. Another approach is to use richer continuous distributions, such as  normalizing flows~\citep{rezende2015variational, ward2019improving}. In this work, we restrict ourselves to the multicategorical setting, which is sufficient to get satisfying results (Sec.~\ref{subsec:results}), and we leave the other options for future work.

\section{RELATED WORK}
\label{sec:related}
\paragraph{Similar parametrizations.} Other algorithms use similar parametrization. First, Path Consistency Learning (PCL,~\citep{nachum2017bridging}) also parametrize the $Q$-value as a sum of a log-policy and a value. Trust-PCL~\citep{nachum2017trust}, builds on PCL by adding a trust region constraint on the policy update, similar to our KL regularization term. A key difference with IQ is that (Trust-)PCL is a residual algorithm, while IQ works around a fixed-point scheme. Shortly, Trust-PCL can be seen as a version of IQ without the target value network $V_{\bar\phi}$. These entropy-regularized residual approaches are derived from the softmax temporal  consistency principle, which allows to consider extensions to  a specific form of multi-step learning (strongly relying on the residual aspect), but they also come with drawbacks, such as introducing a bias in the optimization when the environment is stochastic~\citep{geist2016bellman}.
\citet{dai2018sbeed} proposed SBEED (Smooth Bellmann Error Embedding) to address this bias by replacing the residual minimization with a saddle-point problem. They provide an unbiased algorithm, but that ultimately requires to solve a min-max optimization, more complex than what we propose.
Second, Quinoa~\citep{degrave2019quinoa}  uses a similar loss to Trust-PCL and IQ (without reference to the former Trust-PCL), but does not propose any analysis, and is evaluated only on a few tasks.
Third, Normalized Advantage Function (NAF,~\citet{gu2016continuous}) is designed with similar principles. In NAF, a $Q$-value is parametrized as a value and and an advantage, the latter being quadratic on the action. It matches the special case of IQ with a Gaussian policy, where we recover this quadratic parametrization.
Finally, the action branching architecture~\citep{tavakoli2018action} was proposed to emulate Dueling Networks in the continuous case, by using a similar $Q$-value parametrization with a multicategorical policy representation. This architecture is recovered by IQ in the case $\alpha=0$ and $\tau \rightarrow 0$.
\paragraph{Regularization.} Entropy and KL regularization are used by many other RL algorithms. Notably, from a dynamic programming perspective, IQ-DP(0, $\tau$) performs the same update as SAC -- an entropy regularized VI. This equivalence is however not true in the function approximation regime. Due to the empirical success of SAC and its link to IQ, it will be used as a baseline on continuous control tasks. Other algorithms also use KL regularization, \emph{e.g.} Maximum a posteriori Policy Optimization (MPO,~\citet{abdolmaleki2018maximum}). We refer to~\citet{vieillard2020leverage} for an exhaustive review of algorithms encompassed within the MD-VI framework.


\section{EXPERIMENTS}
\looseness=-1


\paragraph{Environments and metrics.} We evaluate IQ first on the OpenAI Gym environment~\citep{brockman2016openai}. It consists of $5$ locomotion tasks, with action spaces ranging from $3$ (Hopper-v2) to $17$ dimensions (Humanoid-v2). We use a rather long time horizon setting, evaluating our algorithm on $20$M steps on each environments. We also provide result on the Adroit manipulation dataset~\citep{rajeswaran2017learning}, with a similar setting of $20$M environment steps. Adroit is a collection of $4$ hand manipulation tasks, often used in an offline RL setting, but here we use it only as a direct RL benchmark. Out of these $4$ tasks, we only consider $3$ of them: we could not find any working algorithm (baseline or new) on the ``relocate'' task. To summarize the performance of an algorithm, we report the baseline-normalized score along iterations: It normalizes the score so that $0\%$ corresponds to a random score, and $100\%$ to a given baseline. It is defined for one task as
$\text{score} = \frac{\text{score}_\text{algorithm} - \text{score}_\text{random}}{\text{score}_\text{baseline} - \text{score}_\text{random}}$,
where the baseline is the best version of SAC on Mujoco and Adroit after $20$M steps. We report aggregated results, showing the mean and median of these normalized scores along the tasks. Each score is reported as the average over $20$ random seeds. For each experiment, the corresponding standard deviation is reported in Appx.~\ref{subappx:results}.

\looseness=-1
\paragraph{IQ algorithms.} We implement IQ with the Acme~\citep{hoffman2020acme} codebase. It defines two deep neural networks, a policy network $\pi_\theta$ and a value network $V_\phi$. IQ interacts with the environment through $\pi_\theta$, and collect transitions that are stored in a FIFO replay buffer. At each interaction, IQ updates $\theta$ and $\phi$ by performing a step of stochastic gradient descent with  Adam~\citep{kingma2014adam} on $\mathcal{L}_{\text{IQ}}$ (Eq.~\eqref{eq:IQ:loss}). During each step, IQ updates a copy of the weights $\theta$, $\bar\theta$, with a smooth update $\bar\theta \leftarrow (1-\lambda)\bar\theta + \lambda\theta$, with $\lambda\in(0,1)$. It tracks a similar copy $\bar\phi$ of $\phi$. We keep almost all common hyperparameters (networks architecture, $\lambda$, etc.) the same as our main baseline, SAC. We only adjust the learning rate for two tasks, Humanoid and Walker, where we used a lower value: we found that IQ benefits from this, while for SAC we did not observe any improvement (we provide more details and complete results in Appx.~\ref{subappx:results}). Our value network has the same architecture as the SAC $Q$-networks except that the input size is only the state size (as it does not depend on the action). The policy network has the same architecture as the SAC policy network, and differs only by its output: IQ policy outputs a multicategorical policy (so $n\cdot d$ values, where $d$ is the dimensionality of the action space and $n$ is the number of discrete action on each dimension), while SAC policy outputs $2$ $d$-dimensional vectors (mean and diagonal covariance matrix of a Gaussian). We use $n=11$ in our experiments. IQ relies on two other hyperparameters, $\alpha$ and $\tau$. We selected a value of $\tau$ per task suite: $10^{-2}$ on Gym tasks and $10^{-3}$ on Adroit. To make the distinction between the cases when $\alpha=0$ and $\alpha>0$, we denote IQ($\alpha>0$) as M-IQ, for Munchausen-IQ, since it makes use of the Munchausen regularization term. For M-IQ, we found $\alpha=0.9$ to be the best performing value, which is consistent with the findings of~\citet{vieillard2020munchausen}. We report a empirical study of these parameters in the next part of this Section.
Extended explanations are provided in Appx.~\ref{subappx:pc}.

\begin{figure}
    \centering
        \includegraphics[width=\linewidth]{figures/nlc_mujoco_mean_20s_full_best.pdf}
        \includegraphics[width=\linewidth]{figures/nlc_adroit_mean_20s.pdf}
\vspace{-15pt}
     \caption{SAC-normalized mean scores on Gym (\textbf{top}) and Adroit (\textbf{bottom}).}
    \label{fig:mujoco_iq}
    \label{fig:ablation}
    \label{fig:adroit_iq}
\vspace{-8pt}
\end{figure}

\looseness=-1
\label{subsec:results}
\label{sec:results}
\begin{figure*}
    \centering
    \includegraphics[width=\linewidth]{figures/mujoco_all_best_20s_merged_120.pdf}
    \vspace{-20pt}
        \caption{Scores on \textbf{\textcolor{Red}{Gym}} and \textbf{\textcolor{Plum}{Adroit}}. Vertical bars denote +/- empirical standard deviation over $20$ seeds.}
    \label{fig:mujoco_temp}
\end{figure*}

\paragraph{Baselines.} On continuous control tasks, our main baseline is SAC, as it reaches state-of-the-art performance on Mujoco tasks. We compare to the version of SAC that uses an adaptive temperature for reference, but note that for IQ we keep a fixed temperature ($\tau$) setting. To reach its best performance, SAC either uses a specific temperature value per task, or an adaptive scheme that controls the entropy of the policy. This method could be extended to multicategorical policies, but we leave this for future work, and for IQ we use the same value of $\tau$ for all tasks of an environment. We use SAC with the default parameters from~\citet{haarnoja2018soft2} on Gym, and a specifically tuned version of SAC on Adroit. Remarkably, SAC and IQ work with similar hyperparameter ranges on both benchmarks. We only found that using a learning rate of $3\cdot10^{-5}$ (instead of $3\cdot10^{-4}$) gave better performance on Adroit. We also compare IQ to Trust-PCL. It is the closest algorithm to IQ, with a similar parametrization (SBEED also has this parametrization, but all the environments we consider here have detreministic dynamics, and thus there is no bias issue, see Sec.~\ref{sec:related}). To be fair, we compare to our version of Trust-PCL, which is essentially a residual version of IQ, where the target value network $V_{\bar\phi}$ is replaced by the online one. We use Trust-PCL with a fixed temperature, and we tuned this temperature to the environment. We found that Trust-PCL reaches its best performance with significantly lower values of $\tau$ compared to IQ. In the ablation (Fig.~\ref{fig:ablation}) we used $\tau=10^{-4}$ for PCL and Trust-PCL.




\paragraph{Comparison to baselines.} We report aggregated results of IQ and M-IQ on Gym and Adroit in Fig.~\ref{fig:adroit_iq} (median scores can be found in Appx.~\ref{subappx:results}). IQ reaches competitive performance to SAC. It is less sample efficient on Gym (SAC reaches higher performance sooner), but faster on Adroit, and IQ reaches a close final performance on both environments. Detailed scores in Fig.~\ref{fig:mujoco_temp} show how the performance varies across environments. Specifically, IQ outperforms SAC on $3$ of the $8$ considered environments: Ant, Hopper, and Door. On the $5$ others, SAC performs better, but IQ and M-IQ still reach a reasonable performance. Moreover, on almost all environments, all mean performances are within the same confidence interval (Humanoid, and to a less extent HalfCheetah, being notable exceptions, in favor of SAC). The difference in performance between IQ and M-IQ represents the impact of the Munchausen term (\textit{i.e} KL regularization). It is never detrimental, and can even bring some improvement on Gym, but is clearly less useful than in discrete action. Indeed, M-DQN~\citep{vieillard2020munchausen} is designed with the same $\alpha$ parameter but is tailored for discrete actions, and empirically clearly benefits from using $\alpha>0$. We conjecture that this discrepancy comes from the inductive bias we introduce with the multicategorical policy, that could lessen the effect of the Munchausen trick.













\paragraph{Influence of the hyperparameters.} (M)-IQ relies on three key hyperparameters: the temperature $\tau$, the Munchausen coefficient $\alpha$, and the number of bins $n$. The influence of $\alpha$ can be understood as the difference between IQ and M-IQ, discussed above. For the two others parameters, we study their influence with two sweeps, for which we report learning curves in Appx~\ref{subappx:results}. IQ seems to be robust enough to the number of bins, and $n$ turns out to be rather easy to tune: values of $n$ between $7$ and $15$ give similar results. On the other hand, we find that  $\tau$ needs to be selected carefully: while it helps learning, too high values of $\tau$ can be detrimental to the performance, and it highlights that its optimal value might be dependant on the task. In the end, $\tau$ has more influence on IQ than $\alpha$ or $n$, and stands out to be the key element to tune within IQ; thus, adapting the automatic scheduling of the temperature from SAC looks like a promising research direction.




\looseness=-1
\paragraph{Ablation study.} We perform an ablation on important components of IQ in Fig.~\ref{fig:ablation}. \textbf{(1)} We replace the target network by its online counterpart in Eq.~\eqref{eq:IQ:loss}, which gives us Trust-PCL (PCL is obtained by setting $\alpha=0$), a residual version of our method. IQ and M-IQ both outperform Trust-PCL and PCL on Mujoco. \textbf{(2)} We use a Gaussian parametrization of the policy instead of a multicategorical distribution. We observe on Fig.~\ref{fig:ablation} that this causes the performance to drop drastically. This validates the considerations about the necessary complexity of the policy from Section~\ref{sec:practical}.

\section{CONCLUSION}
\looseness=-1
We introduced IQ, a parametrization of a $Q$-value that mechanically preserves the softmax relation between a policy and an implicit $Q$-function. Building on this parametrization, we derived an off-policy algorithm, that learns a policy and a value by minimizing a single loss. We provided insightful analysis that justifies our algorithm and creates meaningful links with the literature (notably with the dueling networks architecture). Specifically, IQ performs entropy and implicit KL regularization on the policy. This kind of regularization was already used and analyzed in RL, but was limited by the difficulty of estimating the softmax of $Q$-function in continuous action settings. IQ ends this limitation by avoiding any approximation in this softmax, effectively extending the analysis of this regularization. This parametrization comes at a cost: it shifts the representation capacity from the $Q$-network to the policy, which makes the use of Gaussian representation ineffective. We solved this issue by considering multicategorical policies, which allowed IQ to reach performance comparable to state-of-the-art methods on classic continuous control benchmarks. Yet, we envision that studying richer policy classes may results in even better performance. In the end, this work brings together theory and practice: IQ is a theory-consistent manner of implementing an algorithm based on regularized VI in continuous actions settings.


\bibliographystyle{plainnat}
