2
$\begingroup$

I have it from relevant authority that MDP formulation of reinforcement learning is:

  1. At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$
  2. Then, for t = 0 until done:
    • Agent selects action $a_t$
    • Environment samples reward $r_t \sim R(.|s_t, a_t)$
    • Environment samples next state $s_{t+1} \sim P(.|s_t, a_t)$
    • Agent receives reward $r_t$ and next state $s_{t+1}$

Question: Is the reward not a single number given $a_t, s_{t+1}$ and $s_t$? If we are sampling $s_{t+1}$ then sampling reward as well does not make sense to me. I think the process should instead be:

  1. At time step t = 0 environemnt samples initial state $s_0 \sim p(s_0)$
  2. Then, for t = 0 until done:
    • Agent selects action $a_t$
    • Environment samples reward $\require{enclose} \enclose{horizontalstrike}{r_t \sim R(.|s_t, a_t)}$
    • Environment samples next state $s_{t+1} \sim P(.|s_t, a_t)$
    • Agent receives reward $\require{enclose}\enclose{horizontalstrike}r_t$ $r_t|(s_t, s_{t+1}, a_t)$ and next state $s_{t+1}$
Improve this question
$\endgroup$
5
  • $\begingroup$ The reward you get at stage $t$ does not depend on $s_{t+1}$. It may depend on the action $a_t$. It may also be random. Your definition allows for non-Markovian processes, because the reward you receive at a given stage depends on state occupancies at different stages. $\endgroup$
    – jbowman
    Jun 3, 2018 at 15:42
  • $\begingroup$ en.wikipedia.org/wiki/Markov_decision_process#Definition $\endgroup$
    – figs_and_nuts
    Jun 3, 2018 at 15:52
  • $\begingroup$ That formulation is not actually correct. Consider a one-period MDP, where there is no future state, or the reward you get at the final stage of a finite MDP, where again there is no future state. The definition as given compresses two distinct concepts - receiving the reward and transitioning into the next state - into one. It is true that for, probably, the vast majority of MDPs, the Wikipedia definition will work just fine, but, referring to Puterman (in the next comment)... $\endgroup$
    – jbowman
    Jun 3, 2018 at 16:03
  • $\begingroup$ "As a result of choosing action $a \in A_s$ in state $s$ at decision epoch $t$, 1) The decision-maker receives a reward $r_t(s,a)$ and 2) the system state at the next epoch is determined by the probability distribution $p_t(\cdot|s,a)$." (Markov Decision Processes, p. 19 of my edition). $\endgroup$
    – jbowman
    Jun 3, 2018 at 16:04
  • $\begingroup$ @jbowman Letting $r_t$ depend only on $s_t$ and $a_t$, or additionally letting it also depend on $s_{t+1}$, is kind of equivalent. $s_{t+1}$ itself is determined by $s_t$ and $a_t$, so any influence that $s_{t+1}$ may have on $r_t$ can be considered to be, say "baked in" in the influence that $s_t$ and $a_t$ have on $r_t$. $\endgroup$
    – Dennis Soemers
    Jun 4, 2018 at 10:57

1 Answer 1

Reset to default
2
$\begingroup$

For the theoretical basis of reinforcement learning, in the MDP model we care about the Markov property - that the state $s_t$ captures all necessary information to define the distributions of $r_t$ [many sources would use $r_{t+1}$ conventionally] and $s_{t+1}$ given $a_t$.

The two values $r_t$ and $s_{t+1}$ can be derived in multiple different ways, and don't have to be sampled separately. They can be sampled separately, or they can be correlated - the important detail is that the knowable distribution of $r_t$ and $s_{t+1}$ only depends on $s_t$.

The reward system can be set up fairly arbitrarily depending on the goals of the agent. Your idea that reward should be deterministic single value based on the observed $(s_t, a_t, s_{t+1})$ defines a valid MDP, but does not cover all possible MDPs.

The slide from the tutorial you link and quote is also a valid MDP. It is not showing how the elements $r_t$ and $s_{t+1}$ are being sampled. The notation implies independent uncorrelated samples generated from the environment, which is an option. However, I think that is just a detail that has been skipped over - in practice the environment progresses according to its rules, and the sampling of reward and next state are correlated in time.

In addition to depending on any combination of $(s_t, a_t, s_{t+1})$, a reward $r_t$ may have a stochastic element. Reward schemes can be stochastic for a variety of reasons, although the situation does not often turn up in the toy examples used to teach RL.

There are two subtly different cases I can think of:

  • The reward is not a direct property of the state, but a consequence of it, subject to unmeasurable and unknowable fluctuations. For instance, in a chemical reactor vessel, you might have actions to add reagents, heat and/or stir the mixture at a certain rate. The reward could be the amount of a desired product that is made. The state would be the measurable concentrations of reagents, current temperature and motion. The reward would fluctuate depending on things you cannot realistically measure or know (you might also try to model these as a POMDP, but it is relatively common to treat physical measurement limitations as stochastic variation).

  • The reward is determined randomly by the environment. For instance, in a fantasy fighting game, where your goal is to collect gold by fighting monsters, the treasure dropped by a defeated monster might be randomly chosen according to the type of monster.

There are probably other similar cases and examples.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Amazing explanation. Directly addresses the question asked. But, I am afraid what i wanted to ask is not exactly what i ended up asking in the question. It is that i know the $a_t$ before sampling the reward so the deterministic single value reward that i suggest will be a function of $a_t$ as well. Please read the edit. I apologize i wasted your time. Kindly, edit the answer accordingly $\endgroup$
    – figs_and_nuts
    Jun 3, 2018 at 20:30
  • $\begingroup$ Can you provide me an example where given $(a_t, s_t, s_{t+1})$ there might be different rewards for different runs? $\endgroup$
    – figs_and_nuts
    Jun 4, 2018 at 8:17
  • $\begingroup$ I did not get that example in its essence the way i got others. Not a man of finance. anyhow, speaking of : $r_t$ determined by $s_{t}$ and independent of both $a_t$ and $s_{t+1}$ Is this not a function of $a_t$ and $s_{t+1}$? for example $f(x) = 5$ $\endgroup$
    – figs_and_nuts
    Jun 4, 2018 at 9:55
  • $\begingroup$ @MiloMinderbinder I have updated the answer to focus more on this "rewards may also be stochastic" aspect. $\endgroup$
    – Neil Slater
    Jun 4, 2018 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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