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.


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.