2
$\begingroup$

Do we have to consider if (s is given) an action a can lead to s' when defining a reward function?

To be more specific: Let's say I have a 1D Map like: |A|B|C|D| To define a reward function, I simply defined a matrix for every action, where the columns and rows represent the states (A-D) and the entries represent the reward. But I made it even simpler. As reaching a specific state gives a reward of 1 I just assigned the reward to a column (C).

$$ \begin{matrix} -1&0&1&0\\ -1&0&1&0\\-1&0&1&0\\-1&0&1&0 \end{matrix} $$ However, lets say the matrix is specified for the action "going right". Now there are entries reading: D ==> going right ==> C getting reward of 1. This is actually not possible. However, I thought the transition function would handle this issue since I will define there what is possible and what is not. But anyway it is said that for a horizon of one the immidiate reward is given and the transition function isn't even considered. This leads to arbitrary result. So do I have to consider the "physics" of my world?

$\endgroup$
  • $\begingroup$ Regarding " But anyway it is said that for a horizon of one the immidiate reward is given and the transition function isn't even considered" - could you reference where you have read this. It is entirely wrong, but perhaps it is taken out of context or a misunderstanding $\endgroup$ – Neil Slater Mar 23 '19 at 9:20
0
$\begingroup$

Your issue is related to how you are representing your rewards, and not anything to worry about for the MDP.

You have chosen to use a matrix to represent your reward function, which maps $(s,s')$ to $r$. If some transition $s \rightarrow s'$ doesn't happen, then it doesn't matter at all what you put there for the reward value for $(s,s')$. It is only because you have decided to use a matrix for this that you even need to think about it.

A complete reward function would map $s, a, s'$ to a scalar value, and can also include a random factor. You don't need to use all the factors - a MDP can use any or all of them, and all the MDP theory is still correct. In your case, it looks like arriving in a "goal state" $s' = C$ is what triggers a +1 reward. So instead of a matrix you could define a function:

$$r(s,a,s') = \begin{cases} -1,& \text{if } s' = A\\ 1,& \text{if } s' = C\\ 0, & \text{otherwise} \end{cases} $$

This is equally valid in the MDP as your matrix, and avoids the issue of storing data about impossible transitions.

I thought the transition function would handle this issue since I will define there what is possible and what is not.

Yes that should be the case. If your transition function does not allow for certain state changes, then there is no need to handle them in any particular way in the reward function.

But anyway it is said that for a horizon of one the imm[e]diate reward is given and the transition function isn't even considered

I am not sure where you have read this, but it does not relate to your representation issue or resolving "impossible" state transitions.

If you are using a model-based method, such as Policy Iteration or Value Iteration, then you do use the transition function and reward function - more or less directly in the form of the Bellman equations. In this case, the transition function will assign a weight of 0 to the impossible transitions, so the reward value doe not matter (and efficient code would likely skip even looking up or calculating the reward in that case).

If you are using a model-free method, such as Q learning, then the agent does not use the transition function or the reward function directly. They are part of the environment that it is learning. However, any code for the simulated environment has to implement the physics of your world, and that includes using the transition function to resolve what happens when the agent takes an action. In that case, the simulated model of the environment would prevent the agent ever experiencing impossible transitions, so there is never any need to calculate the reward for them or allow for them as edge cases in a reward function (you might still choose to check validity and/or return something as defensive programming of the reward function, but it is not required for the MDP and reinforcement learning to work).

$\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.