1
$\begingroup$

Sorry for the wall of text below. It will seem like forever before my question comes up, but I think the context is much needed to avoid confusion.

According to "A Generalized Reinforcement Learning Model: Convergence and Applications" by Michael L. Littman and Csaba Szepesvári, the following theorem holds:

Theorem: For contraction mapping $T$ with fixed point $V^*$, some arbitrary value function $V_0$, and some approximation of $T$ based on two value functions (denoted as $T_t(V_1, V_2)$) , define $V_{t+1} = T_t(V_t, V_t)$. The claim is that $V_{t+1}$ converges to $V^*$ if there exist $\forall x, 0 \leq a_t(x) \leq 1$, $0 \leq \gamma < 1$ such that following hold:

  1. For all $U1$, $U2$, and $x$: $|T_t(U1,V^*)(x) - T_t(U2,V^*)(x)| \leq (1-a_t(x))|U1(x) - U2(x)|$

  2. For all $U$, $V$, and $x$: $|T_t(U,V^*)(x) - T_t(U,V)(x)| \leq \gamma a_t(x)\sup_{x'}|V^*(x') - V(x')|$

  3. For all $x$, $\sum_{t}{a_t(x)} = \infty$, $\sum_t{a_t^2(x)} < \infty$

This does hold true for the standard Q learning algorithm, where given the observed transition $(s, a, s', R(s, a))$ at time t, we define $$T_t(Q,W)(s,a) = Q(s,a) + a_t(s,a)(R(s,a) + \gamma \max_{a'} W(s', a')-Q(s,a))$$ Where the choice of $\gamma$ and $a_t$ matches the conditions. See below for how it easily fulfills the requirements, probably since the theorem was designed for it:

Pf 1. $$|T_t(U1,V^*)(s,a) - T_t(U2,V^*)(s,a)|\\ =|U1(s,a) + a_t(s,a)(R(s,a) + \gamma \max_{a'} V^*(s',a')-U1(s,a)) \\ - U2(s,a) - a_t(s,a)(R(s,a) - \gamma \max_{a'} V^*(s',a')+U2(s,a))| \\ \leq (1-a_t(s,a))|U1(s,a) - U2(s,a)|$$

Pf 2. $$|T_t(U,V^*)(s,a) - T_t(U,V)(s,a)|\\ =|U(s,a) + a_t(s,a)(R(s,a) + \gamma \max_{a'} V^*(s',a')-U(s,a)) \\ - U(s,a) - a_t(s,a)(R(s,a) - \gamma \max_{a'} V(s',a')+U(s,a))| \\ = \gamma a_t(s,a)|(\max_{a'} V^*(s', a') - \max_{a'} V(s',a')| \\ \leq \gamma a_t(s,a)\sup_{s', a'}|V^*(s',a') - V(s',a')| \text{ (by non-expansion)}$$

But I'm wondering how the theorem still holds for a generalized Markov Decision Process problem, where a general Bellman equation holds:

$$Q^*(s,a) = R(s,a) + ⊕_{s'}^{s,a}(\gamma ⊗_{a'}^{s'}(Q^*(s', a')))$$

with any non expansion operators $⊕_{s'}^{s,a}$ (an operator that summarizes over all next states) and $⊗_{a'}^{s'}$ (an operator that dictates how future actions are to be chosen).

For example, in the vanilla Markov Decision Process problem, with $T(s,a,s')$ being the transition probability from state $s$ to $s'$ when action $a$ is chosen, we define $⊕_{s'}^{s,a}(F(s')) = \sum_{s'}T(s,a,s')F(s')$ and $⊗_{a'}^{s'}(G(a')) = \max_{a'}G(a')$.

I think I can see how any valid choice of $⊗_{a'}^{s'}$ can still result in a learnable Markov Decision Process solution if you use a modified Q learning algorithm, with $$T_t(Q,W)(s,a) = Q(s,a) + a_t(s,a)(R(s,a) + \gamma ⊗_{a'}^{s'}(W(s', a'))-Q(s,a))$$

The Pf 1. and Pf 2. proof steps still work exactly the same way, with the $⊗_{a'}^{s'}$ replacing the $\max_{a'}$, so the algorithm converges to the solution as needed.

But I'm really confused about how $⊕_{s'}^{s,a}$ plays a role at all in the convergence proof. I can't find a place to incorporate the $⊕_{s'}^{s,a}$ operator in the Q learning algorithm.

The only way $⊕_{s'}^{s,a}$ could affect the proof of convergence is how it changes what $V^*$ is. But actually, the Pf 1. and Pf 2. steps work perfectly fine regardless of what $V^*$ is, so the proof is basically saying that the Q-learning algorithm will converge to an arbitrary value function, which is obviously not true.

I know that empirically, the $V^*$ that the Q learning algorithm will converge to is the one that uses $⊕_{s'}^{s,a}(F(s')) = \sum_{s'}T(s,a,s')F(s')$. It doesn't seem obvious how the Q learning algorithm or the convergence theorem proof uses this fact though.

Did I misunderstand the statement of the paper's converging theorem? I've read the paper and can't quite find what condition I missed or understood incorrectly. Did I miss a subtlety that actually makes Pf 1. and Pf 2. invalid? I don't have enough experience in this field to tell.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.