# Proving facts in inverse reinforcement learning [closed]

I was going through paper titled "Algorithms for Inverse Reinforcement Learning" by Andrew Ng and Russell.

It states following basics:

• MDP $$M$$ is a tuple $$(S,A,\{P_{sa}\},\gamma,R)$$, where

• $$S$$ is a finite seto of $$N$$ states
• $$A=\{a_1,...,a_k\}$$ is a set of $$k$$ actions
• $$\{P_{sa}(.)\}$$ are the transition probabilities upon taking action $$a$$ in state $$s$$.
• $$R:S\rightarrow \mathbb{R}$$ is a reinforcement function (I guess its what it is also called as reward function) For simplicity in exposition, we have written rewards as $$R(s)$$ rather than $$R(s,a)$$; the extension is trivial.
• A policy is defined as any map $$\pi : S \rightarrow A$$

• Bellman Equation for Value function $$V^\pi(s)=R(s)+\gamma \sum_{s'}P_{s\pi(s)}(s')V^\pi(s')\quad\quad...(1)$$

• Bellman Equation for Q function $$Q^\pi(s,a)=R(s)+\gamma \sum_{s'}P_{sa}(s')V^\pi(s')\quad\quad...(2)$$

• Bellman Optimality: The policy $$\pi$$ is optimal iff, for all $$s\in S$$, $$\pi(s)\in \text{argmax}_{a\in A}Q^\pi(s,a)\quad\quad...(3)$$

• All these can be represented as vectors indexed by state, for which we adopt boldface notation $$\pmb{P,R,V}$$.

• Inverse Reinforcement Learning is: given MDP $$M=(S,A,P_{sa},\gamma,\pi)$$, finding $$R$$ such that $$\pi$$ is an optimal policy for $$M$$

• By renaming actions if necessary, we will assume without loss of generality that $$\pi(s) = a_1$$.

Paper then states following theorem, its proof and a related remark:

Theorem: Let a finite state space $$S$$, a set of actions $$A=\{a_1,..., a_k\}$$, transition probability matrices $${\pmb{P_a}}$$, and a discount factor $$\gamma \in (0, 1)$$ be given. Then the policy $$\pi$$ given by $$\pi(s) \equiv a_1$$ is optimal iff, for all $$a = a_2, ... , a_k$$, the reward $$\pmb{R}$$ satisfies $$(\pmb{P}_{a_1}-\pmb{P}_a)(\pmb{I}-\gamma\pmb{P}_{a_1})^{-1}\pmb{R}\succcurlyeq 0 \quad\quad ...(4)$$ Proof:
Equation (1) can be rewritten as
$$\pmb{V}^\pi=\pmb{R}+\gamma\pmb{P}_{a_1}\pmb{V}^\pi$$
$$\therefore\pmb{V}^\pi=(\pmb{I}-\gamma\pmb{P}_{a_1})^{-1}\pmb{R}\quad\quad ...(5)$$
Putting equation $$(2)$$ into $$(3)$$, we see that $$\pi$$ is optimal iff
$$\pi(s)\in \text{arg}\max_{a\in A}\sum_{s'}P_{sa}(s')V^\pi(s') \quad...\forall s\in S$$
$$\iff \sum_{s'}P_{sa_1}(s')V^\pi(s')\geq\sum_{s'}P_{sa}(s')V^\pi(s')\quad\quad\quad\forall s\in S,a\in A$$ $$\iff \pmb{P}_{a_1}\pmb{V}^\pi\succcurlyeq\pmb{P}_{a}\pmb{V}^\pi\quad\quad\quad\forall a\in A\text{\\} a_1 \quad\quad ...(6)$$ $$\iff\pmb{P}_{a_1} (\pmb{I}-\gamma\pmb{P}_{a_1})^{-1}\pmb{R}\succcurlyeq\pmb{P}_{a} (\pmb{I}-\gamma\pmb{P}_{a_1})^{-1}\pmb{R} \quad\quad \text{...from (5)}$$
Hence proved.

Remark: Using a very similar argument, it is easy to show (essentially by replacing all inequalities in the proof above with strict inequalities) that the condition $$(\pmb{P}_{a_1}-\pmb{P}_a)(\pmb{I}-\gamma\pmb{P}_{a_1})^{-1}\pmb{R}\succ 0$$ is necessary and sufficient for $$\pi\equiv a_1$$ to be the unique optimal policy.

I dont know if above text from paper is relevant for what I want to prove, still I stated above text as a background.

I want to prove following:

1. If we take $$R : S → \mathbb{R}$$—there need not exist $$R$$ such that $$π^*$$ is the unique optimal policy for $$(S, A, T, R, γ)$$
2. If we take $$R : S × A → \mathbb{R}$$. Show that there must exist $$R$$ such that $$π^*$$ is the unique optimal policy for $$(S, A, T, R, γ)$$.

I guess point 1 follows directly from above theorem as it says "$$\pi(s)$$ is optimal iff ..." and not "unique optimal iff". Also, I feel it also follows from operator $$\succcurlyeq$$ in equation $$(6)$$. In addition, I feel its quite intuitive: if we have same reward for any given state for every action, then different policies choosing different actions will yield same reward from that state hence resulting in same value function.

I dont feel point 2 is correct. I guess, this directly follows from the remark above which requires additional condition to hold for $$\pi$$ to be "uinque optimal" and this condition wont hold if we simply define $$R : S × A → \mathbb{R}$$ instead of $$R : S → \mathbb{R}$$. Additionally, I feel, this condition will hold iff we had $$=$$ in equation $$(3)$$ instead of $$\in$$ (as this will replace all $$\succcurlyeq$$ with $$\succ$$ in the proof). Also this also follow directly from point 1 itself. That is we can still have same reward for all actions from given state despite defining reward as $$R : S × A → \mathbb{R}$$ instead of $$R : S → \mathbb{R}$$, which is the case with point 1.

Am I correct with the analysis in last two paragraphs?

Update

After some more thinking, I felt I was doing it all wrong. Also I feel the text from the paper which I specified is of not much help in proving these two points. So let me restate new intuition for proofs for the two points:

1. For $$R: S\rightarrow \mathbb{R}$$, if some state $$S_1$$ and next state $$S_2$$ has two actions between them, $$S_1-a_1\rightarrow S_2$$ and $$S_1-a_2\rightarrow S_2$$, and if optimal policy $$π_1^*$$ chooses $$a_1$$, then $$π_2^*$$ choosing $$a_2$$ will also be optimal, thus making NONE "uniquely" optimal since both $$a_1$$ and $$a_2$$ will yield same reward as reward is associated with $$S_1$$ instead of with $$(S_1,a_x)$$.

2. For $$R: (S,A)\rightarrow\mathbb{R}$$, we can assign large reward say $$+∞$$ to all actions specified in given $$π^*$$ and $$-∞$$ to all other actions. This reward assignment will make $$π^*$$ a unique optimal policy.

Are above logics correct and enough to prove given points?

• Please ask only one question per post. We discourage "is my answer correct?" questions, as they are unlikely to be useful to others in the future. – D.W. Mar 15 at 18:35
• The two questions are very related. If I have to ask them on separate post, then I have to copy paste the whole background, which will be a lot of redundancy. Also any future visitor will gain a lot by reading the two problems together, instead of reading one and not realising that theis is separate post for the other very closely related problem. Even if he/she realizes, he will have to figure out what is difference in two by comparing two posts. Also I havent just asked if X is correct. I have specified two separate analysis for my two attempts. – Rnj Mar 15 at 20:40
• – D.W. Mar 15 at 21:57
• I’m voting to close this question because it was cross-posted. – D.W. Mar 15 at 21:57
• What is real reason for closing this question? Is it cross posting or being off topic? I asked this question on both those site some days back but got no reply. Yesterday, on datascience.stackexchange, I got comment that theoretical questions are off-topic and I better ask on cs.stackexchange. Where should I go to get answers ???!!! – Rnj Mar 16 at 8:21