1
$\begingroup$

Going through some tutorials on reinforcement learning, I cannot help but to notice that people selectively put expectation operators around their equations (value, Q, loss, etc.), and when expectation is used, it is never evaluated.

Note: By "evaluated", I mean, if I were asked in a probability exam to find the expectation of $X$, where $X \sim \mathcal{N}(\mu, \sigma^2)$ is the Gaussian distribution, I would write $E(f_X(x)) = \mu$. If it were the uniform random variable, I would write $E(f_X(x)) = \dfrac{1}{n}$. It would be unthinkable for me to leave it as $E(f_X(x))$, but this is exactly what people in reinforcement learning does.

The usage of the expectation is also irregular:

For example, in these papers, expectation is not used in the definition of state-action value/function.

https://hmjianggatech.github.io/files/HCK.pdf

https://yilundu.github.io/2016/12/24/Deep-Q-Learning-on-Space-Invaders.html

In these papers, expectations are used

https://arxiv.org/pdf/1511.06581.pdf

http://paulorauber.com/notes/reinforcement_learning.pdf

https://www.nature.com/articles/nature14236.pdf

Finally, it is not clear to me how people can actually implement these expressions as actual algorithms, because the distributions, i.e., the policy, the environment, the reward, are never specified, they are just assumed to exist. More to the point, say that I am given the following definition,

$Q_\pi(s, a) = E_\pi[R_t|s_t = s, a_t = a]$

(as appears http://paulorauber.com/notes/reinforcement_learning.pdf)

However, we do not know what $\pi$ is at the beginning, we only know that it is some probability distribution. Furthermore, it is not clear how the inner expressions i.e. $R_t$.... depends on $\pi$. How do we evaluate this expression as something that is actually implementable in code?

$\endgroup$
2
$\begingroup$

In general, the derivations in RL work with expectations, because it is possible to show important relations analytically, such as Bellman optimality.

In Dynamic Programming, where you have a model, it is possible to expand from an expectation, using known probabilities from the model. Your reference text does this on page 4 for $Q^{\pi}(s,a)$. If you know the policy and environment model, the precise values of Q can be calculated. This is how Policy Iteration and Value Iteration work.

When you have a formula involving an expectation of some value from a system, and access to the system but not its operating parameters (the state transition probabilities in an MDP), it is possible to sample the value, and use that sample in stochastic approximations, because over many samples the eventual average will be the same as the expectation.

Essentially, Q Learning, SARSA, Monte Carlo Control are all algorithms that approximate Value Iteration from Dynamic Programming, by taking samples to resolve expectations in the long term, instead of calculating them over a known probability distribution.

As an aside, often $\pi(a|s)$ is known or under control of the learning agent, so it can be used to partially resolve expectations even when sampling. This knowledge is used in extensions to basic algorithms such as importance sampling and Expected SARSA.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.