1
$\begingroup$

The q value of a specific state,$s$ and action, $a$ is given by the following equation, as per Sutton and Barto's equation 3.13 -

$$q_{\pi}(s,a) = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}|S_t = s, A_t = a]$$

Here, $\gamma$ denotes the discount factor, $t$ the current time step, and $k$ the future time steps. I'm looking for the theoretical maximum value that can be attained by the q value for any state, action, or policy. I'd highly appreciate if someone could evaluate my work and let me know if it could be extended. Also, I'd highly appreciate if someone could point out any shortcomings to my approach or assumptions.

Here's my work -

$$q_{\pi}(s,a) = \mathbb{E}_{\pi}[\gamma^{0}R_{t+1} + \gamma^{1}R_{t+2} + ...|S_t = s, A_t = a]$$

Let $rmax = \max R_t$. This basically says that the agent can encounter various rewards while interacting with the environment. Let's assume the agent obtains the highest possible reward each time.

$$ \leq \mathbb{E}_{\pi}[\gamma^{0}rmax + \gamma^{1}rmax + ...]$$

$$ = \mathbb{E}_{\pi}[rmax * \sum_{k=0}^{k=\infty} \gamma^{k}]$$

We also know that $\sum_{k=0}^{k=\infty} \gamma^{k} = 1/(1-\gamma) \iff |\gamma|<1$

Therefore, the above expression evaluates to $\mathbb{E}_{\pi}[rmax/(1-\gamma)]$

$\endgroup$
2
  • $\begingroup$ What is $\pi$ here and what do you think it happens if you assume an unbounded probability distribution over $R|S,A$? $\endgroup$
    – gunes
    Jul 31, 2022 at 11:13
  • $\begingroup$ $\pi$ is the current policy the agent follows. I think it's safe to say that $R|S,A$ won't be unbounded as rewards are usually set by the algorithm designer. Therefore, the rewards will be bounded within some interval with max and min values. $\endgroup$ Jul 31, 2022 at 15:48

0

Your Answer

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