Is there a mathematical formalism to deal with a missing reward signal?

Typically, a Reinforcement Learning learning problem is formalized as finding an optimal policy for a Markov Decision Process (MDP). In many real-life situations, however, an agent can only get partial information from the environment. For example, Partially Observable MDPs are used to model the case where the agent does not fully observe the state.

I was wondering whether there is any well-established formalism for the case where the agent does not fully observe the reward signal.

In particular, I am thinking about the case where for every state-action pair $$(s, a)$$ the agent receives the reward $$R(s, a)$$ with probability $$1 - \varepsilon$$ and does not receive anything with probability $$\varepsilon$$. Of course, in principle, this setting can be thought as a regular MDP with a stochastic reward, but here I would like the agent to behave optimally w.r.t. to $$R$$.

I would really appreciate if you could point some relevant literature to me!

• This does not directly answer your question (I think), but there are ways of dealing with problems where the reward function (RF) is not specified or it's not easy to specify it correctly. The basic idea is to learn the RF itself (this is sometimes known as inverse RL or reward learning, especially when you are given an optimal policy: that's why it's called IRL because, usually, in an RL problem, you want to find the policy from the RF), but you can also use behaviour cloning (i.e. you don't use a reward function at all, and learn a policy from examples taken from another policy).
– nbro
Dec 1 '21 at 10:13
• @nbro Thanks for the comment! Good point! In fact I asked this question precisely because I am reading about IRL at the moment :) Oversimplifying, RL deals with MDP with observable reward function and IRL deals with the case where the reward function is missing. I was wondering whether some intermediate scenarios have been studied.. Dec 1 '21 at 10:29
• I am not sure if it's intermediate, but in the paper "Inverse Reward Design", if I remember correctly, they formulate the problem of learning a "correct" function from "observed RFs" (i.e. non-optimal or partial/incomplete ones) in a Bayesian/probabilistic setting. So, in a way, if I remember correctly, they kind of combine IRL with RL because they need to solve the RL problem too (but I could be recalling that wrongly, so you may want to check the paper).
– nbro
Dec 1 '21 at 11:00
• Let me know if this answers your question so that I eventually give a formal answer below with this info.
– nbro
Dec 1 '21 at 11:02
• @nbro Thanks a lot for the paper! I'll have a look and I'll let you know! Dec 1 '21 at 15:01

Your setting (of randomly dropping out reward signals) impacts expected future reward by multiply everything by a common factor $$(1-\epsilon)$$.
If the agent is allowed to observe that the reward signal is missing (as opposed to being an observed zero reward), then it could additionally estimate $$\epsilon$$, and correct its learned value function. I would recommend this is handled at the end of training as a separate function instead of modifying $$Q(s,a)$$ during training. That is because initial estimates for $$\epsilon$$ are likely to be inaccurate and make learning even slower (at least for TD learning due to bootstrapping on less accurate values).
The setting becomes more complex if $$\epsilon$$ is made a function of $$a$$, $$s$$ or both, and solutions will be different depending on whether this function is known or unknown.
• Thank you very much! You are totally right.. Yeah, the way I have formulated the problem is actually very trivial, as you correctly noticed. As you pointed out, the situation is less trivial if $\varepsilon$ depends on $s$ and/or $a$. Do you think there could be any other meaningful notion of "partial observability" for the reward function? Nov 30 '21 at 16:43