Meta-review
This paper proposes a new way to do RL in multi-turn dialogue setting where the use of RL is less common compared to the vast success of RL in single-turn case. The proposed approach frames Q-learning as a cross-entropy problem with suitably selected weights such that the trained policy can be used to recover conservative bounds on the Q-value.
While I think the mathematical reasoning here is not important, the reviewers appreciated the mathematical analysis. However, upon going over the mathematical derivations in the paper I noticed that certain steps were not justified. While equation 5 is correct, the next equation isn't justified. It along with the WCE loss assumes that $\mathcal{B}^\star p_\theta$ is in $[0, 1]$ but it isn't clear why this is the case even with assumption 4.1. In particular, if for some $a'$ we have $\pi_\beta(a' \mid s') = 0$, then for a uniform $p_\theta$ we have $\mathcal{B}^\star p_\theta = \infty$. Note that the public comment also points this out. Now, if we assume $\mathcal{B}^\star p_\theta \in [0, 1]$, then we get can complete the proof. These steps are missing in the proof but are as follows:
$\alpha^{(k+1)}(s, a) \ge r(s, a) + \gamma E_{s' \sim P(. | s, a)}[ \max_{a'} \alpha^{(k)}(s', a')]$,
where $\alpha^{(t)}(s, a) = \frac{p^{(t)}(a \mid s)}{\pi_\beta(a \mid s)}$ for any $t \in \mathbb{N}$. Now if you assume convergence that $\lim_{t\rightarrow \infty} \alpha^{(t)}(s, a) = \alpha(s, a)$, we get:
$\alpha(s, a) \ge r(s, a) + \gamma E_{s' \sim P(. | s, a)}[ \max_{a'} \alpha(s', a')]$,
using Bellman optimality,
$Q^\star(s, a) = r(s, a) + \gamma E_{s' \sim P(. | s, a)}[ \max_{a'} Q^\star(s', a')]$
and defining $\delta(s, a) = \alpha(s, a) - Q^\star(s, a)$ and $\delta = \inf_{s, a}\delta(s, a)$, one gets:
$\delta(s, a) \ge \gamma E_{s' \sim P(. | s, a)}[ \max_{a'} \alpha(s', a') - \max_{a'} Q^\star(s', a')] \ge \gamma E_{s' \sim P(. | s, a)}[ \min_{a'} \left( \alpha(s', a') - Q^\star(s', a')\right)] \ge \gamma \delta$,
where the last line uses $\max_x f(x) - \max_x g(x) \ge \min_x (f(x) - g(x))$. Finally, taking inf on LHS means that $\delta \ge \gamma \delta$, which implies $\delta \ge 0$ if $\gamma \in (0, 1)$. Or, $\alpha(s, a) \ge Q^\star(s, a)$. I'd request authors to add justification for why $B^\star p \in (0, 1)$ and these missing steps.
Strengths:
1. Method is simple
2. Experiments are presented for several domains
3. Multi-turn LLM reasoning is an important topic and the use of RL for this has been somewhat less successful. This approach proposes a solution for this.
4. Reviewers appreciated the theoretical result but see below.
Weakness:
1. The theoretical results are at best unjustified and at worst potentially incorrect
2. Requires 3 copies of the model. This makes it expensive in practice as even 2x increase in memory is costly and makes a given approach undesirable. This is important especially given the motivation of the authors to make the Q-learning approach user-friendly.
3. The reviewer ChGQ requested results where the value head is randomly initialized but the authors did not include this study in response. I understand that experiments can be hard to complete during the rebuttal period but this one would have been nice to see.
Overall, my biggest concern is the mathematical foundation of the approach. However, given that the approach works well empirically and is simple and should easy to try, I am leaning towards a weak accept.
Additional comments on reviewer discussion
Reviewers raised the following concerns:
1. Confusion about what turn means (reviewer WNH5). The authors properly addressed this.
2. Effective vocabulary is small (reviewer WNH5). The authors agreed that their experiments do not cover such challenges but that this was more of an artifact of existing benchmarks.
3. Practical effectiveness (3 copies of the model and 2 inference calls): The authors agreed that this is a concern.
4. There were additional writing suggestions that the authors addressed reasonably.
My main concerns are (3) and the theoretical justification the latter which reviewers did not raise. I am still leaning towards acceptance cause there are algorithms such as PPO which are easy to show that they fail theoretically with simple counter-examples but are nevertheless effective in practice. However, the paper shouldn't have steps that are missing justification or at worse wrong maths. So, I request authors to either add justifications or assumptions, or remove the maths as it isn't necessary.