9
$\begingroup$

I was trying to understand MDP's in the context of reinforcement learning, specifically I was trying to understand what the reward function explicitly depends on.

I have seen a formulation of the reward function as defined by Andrew Ng in his lecture notes as:

$$R: S \times A \mapsto \mathbb{R}$$

Which means that the the reward function depends on the current state and the action take at that state and maps to some real number (the reward).

To get a different perspective, I read the interpretation wikipedia had:

The process responds at the next time step by randomly moving into a new state s', and giving the decision maker a corresponding reward $R_a(s,s')$. Which seems to be a different interpretation in my opinion since this would make the reward function more of a function of the form:

$$R: S \times A \times S\mapsto \mathbb{R}$$

Which in my opinion, seems to be a completely different thing. I was trying to understand if the two formulations were actually the same (and if it was possible to prove their equivalence) in the context of MDP's applied to reinforcement learning.

$\endgroup$

4 Answers 4

7
$\begingroup$

The two definitions are not the same, but it essentially boils down to a modelling choice: for some problems, the reward function might be easier to define on the (state,action) pairs, while for others, the tuple (state,action,state) might be more appropriate. There's even a third option that only defines the reward on the current state (this can also be found in some references).

I do think the definition of the reward function R(s,a) on the (state, action) pair is the most common, however. But the core learning algorithms remain the same whatever your exact design choice for the reward function.

$\endgroup$
3
  • $\begingroup$ Basically, it comes down to a modeling choice right? Depending on what actually is feasible to learn? If say R(s,a) is too slow and R(s) is much faster, even if its less accurate, we might choose R(s)? Right? Its basically a choice depending on the application? $\endgroup$ Jan 10, 2015 at 21:19
  • 1
    $\begingroup$ It's not really that one representation is "faster" or "more accurate" than another. It's more than the type of function depends on the domain you are trying to model. For instance, if you simply want to encode in your reward function that some states are "good" (goal states) while others are "bad" (failure states), then the easiest is to encode the reward function as R(s). But if the reward also depend on the system action, then the function R(s,a) is to be preferred. Finally, if the resulting state s' should also be accounted for when determining the reward, R(s,a,s') is best. $\endgroup$ Jan 11, 2015 at 16:05
  • $\begingroup$ @PierreLison do you have any reference on the equivalence of algorithms under those different design ? $\endgroup$ Sep 12, 2023 at 15:04
4
$\begingroup$

In addition to Pierre Lison's answer in favor of a reward function as $ R: S \times A \rightarrow \mathbb{R} $, Sutton and Barto touch on the topic in chapter 3.6 of their book "Reinforcement Learning: An Introduction".

Although the accepted answer is correct in terms of what is most commonly used, they prefer $ \mathcal{R}: S \times A \times S \rightarrow \mathbb{R} $. From said chapter:

In conventional MDP theory, $\mathcal{R}_{ss'}^a $ always appears in an expected value sum [...], and therefore it is easier to use $R_s^a$. In reinforcement learning, however, we more often have to refer to individual actual or sample outcomes. In teaching reinforcement learning, we have found the notation $\mathcal{R}_{ss'}^a $ to be more straightforward conceptually and easier to understand.

$\endgroup$
2
  • $\begingroup$ $R(s,a,s')$ is better according to them because its easier to comprehend? $\endgroup$ Mar 12, 2015 at 18:27
  • 1
    $\begingroup$ with $S \times A \times S $ you mention each component explicitly, while with $S \times A $ you implicitly denote the sum of successive rewards, weighted by probability. as they say: $\mathcal{R}^a_s = \sum_{s'}^S \mathcal{P}_{ss'}^a \mathcal{R}_{ss'}^a $. btw: they probably mean the same by $R $ and $\mathcal{R} $. edit: latex $\endgroup$ Mar 12, 2015 at 18:41
1
$\begingroup$

I think $R(s,a,s')$ is the same thing as $R(s,a)$ in the MDP setting because $s'$ is determined by the transition function $T(s,a)$. Therefore $R(s,a,s')$ becomes $R(s,a,T(s,a))$, which can be simplified as $R(s,a)$.

$\endgroup$
1
  • $\begingroup$ This is ok when $T$ is a function, while it is less direct in the case of $T$ being a markovian kernel.. $\endgroup$ Sep 12, 2023 at 15:06
0
$\begingroup$

They are equivalent in the following sense. Now suppose you have an offline dataset consist of (s1,a1),(s2,a2),..,(sk,ak) with reward r1,r2,...,rk. Based on the data, you can estimate the MDP model with transition probability T(s,a,s') and R(s,a,s'). You can also estimate the MDP model to be T(s,a,s') and R(s,a). Solve these two MDP models theoretically, you should obtain the same results of policy and value.

The above is model-based learning. You can also use the Q-learning method by using the offline dataset in an online fashion (assume that you observe sk,ak,rk sequentially). Obviously, the estimated Q-matrix Q^t(s,a) would be different during the learning as the two forms of reward are different. However, you should obtain the same results of Q(s,a) when it converges. The reason is because P(s,a,s') has already contained the information you need to obtain R(s,a) from R(s,a,s').

$\endgroup$

Your Answer

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

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