2
$\begingroup$

Reading the Retrace paper (Safe and efficient off-policy reinforcement learning) I saw they often use a matrix form of the Bellman operators, for example as in the picture below. How do we derive those forms? Could you point me to some reference in which the matter is explained?

I am familiar with the tabular RL framework, but I'm having trouble understanding the steps from operators to this matrix form. For example, why does $Q^{\pi} = (I -\gamma P^{\pi})^{-1}r$? I know that for the value $V$ we can write \begin{align} V = R + \gamma P^{\pi} V \\ V - \gamma P^{\pi} V = R \\ V (I -\gamma P^{\pi}) = R \\ V = R(I - \gamma P^{\pi})^{-1} \end{align} but this seems slightly different.

Picture from Safe and efficient off-policy reinforcement learning:

Picture from Retrace paper

Improve this question
$\endgroup$
1
  • $\begingroup$ Here you have a related but more general question. $\endgroup$
    – nbro
    Dec 24, 2020 at 12:01

1 Answer 1

Reset to default
2
$\begingroup$

There's not much to derive here it's simply a definition of Bellman operator, it comes from Bellman equation. If you're wondering why \begin{equation} Q^{\pi} = (I - \gamma P^{\pi})^{-1}r \tag{1} \end{equation} they state that $Q^{\pi}$ is a fixed point which means if you apply Bellman operator to it you get the same value \begin{equation} T^{\pi}(Q^{\pi}) = Q^{\pi} \end{equation} You can easily check that since from $(1)$ \begin{equation} r = (I-\gamma P^{\pi})Q^{\pi} \end{equation} if you plug it in definition of Bellman operator you get \begin{align} T^{\pi}(Q^{\pi}) &= r + \gamma P^{\pi} Q^{\pi}\\ &= (I - \gamma P^{\pi})Q^{\pi}+ \gamma P^{\pi} Q^{\pi}\\ &= Q^{\pi} \end{align}

Improve this answer
$\endgroup$
4
  • $\begingroup$ In other words, this proof shows that, if you have some value function $Q^\pi$, such that $r = (I - \gamma P^\pi)Q^\pi$, then $Q^\pi$ is a fixed-point of $T^\pi$. So, to actually answer the question: $Q^{\pi} = (I - \gamma P^{\pi})^{-1}r$ is true because that's what makes $Q^{\pi}$ a fixed point. Note that you could have just used $Q$ (rather than $Q^\pi$) in this derivation, i.e. any value function $Q$ such that $r = (I - \gamma P^\pi)Q$ is a fixed-point. $\endgroup$
    – nbro
    Dec 24, 2020 at 18:23
  • $\begingroup$ What is the exact meaning of the matrix notation in this context? I ask this in particular because the operator $P^{\pi}$ is defined as \begin{equation} (P^{\pi}Q)(s, a) = \sum_{s'}P(s'\vert s, a)\sum_{a'}\pi(a'\vert s') Q(s', a') \end{equation} which makes $P^{\pi}Q$ not being a common matrix-matrix multiplication $\endgroup$
    – Federico Taschin
    Jan 18, 2021 at 15:44
  • $\begingroup$ In particular, isn't here $P^{\pi}$ a tensor? When we use the Bellman operators on the value function we are marginalizing out the actions, but here we apply it explicitly to $Q(s, a)$ for each action, thus $P^{\pi}$ needs to be an $S\times S \times A$ tensor? $\endgroup$
    – Federico Taschin
    Jan 18, 2021 at 16:28
  • $\begingroup$ David Silver lecture (especially slides 22 onwards) can give you more insight into matrix equation, or you can just ask another question on website. $P$ could be a tensor or it could be a matrix of dimensions $(S \times A) \times S$ with appropriate reshaping. $\endgroup$
    – Brale
    Jan 18, 2021 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .