Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper examines the convergence properties of existing RL algorithms for the average reward setting when the MDP satisfies a weaker-than-standard assumption on state visitation.  It requires only weak communication, which means that a subset of states is communicating while others may be transient.  For average-reward methods in particular this in introduces technical challenges because the Q-value function is no longer uniquely defined (up to a constant).  The main result is a proof that 4 algorithms known to converge under stronger assumptions also converge in the weakly-communicating setting.  
strength_and_weaknesses: Describing the strengths of this paper is a bit challenging, in part because I find it lacking in clarity (see below).  There are several things I think I (might) like about the paper, but I am uncertain about how much I like any of them:

1) Extension of prior convergence results to the weakly-communicating setting.  Greater generality is certainly nice from a theoretical perspective, but how much should I care about this result?  The introduction asserts that “it is not rare that an optimal policy introduces multiple recurrent classes”, which would certainly make the extension quite relevant, but the only evidence presented for it seems to be the toy example from Figure 1 and a single citation to Bartlett & Tewari 2009 which is about the generality of this class rather than its importance.  More broadly, the paper is missing any discussion of prior work on weakly-communicating MDPs.

2) Novelty of the technical analysis.  I’m a bit confused because the pitch of the paper is around the weakly communicating setting but Theorem 1 talks about the communicating setting with remark 1 saying weakly-communicating is a minor extension there as well in Theorems 2-4 (which are stated the same way).  From the sketch in 5 and taking a look at the appendix I see that the proof strategy uses the largely the same assumptions as Wan et al. (2021a,b) but replaces their assumption A.8 with new assumptions 9-11.  My guess as to why things are stated the way that they are is that these variant assumptions necessitate some changes to the proof for the communicating case, but as a benefit more easily extend to the weakly-communicating case.  I’m not clear how much a technical delta this represents, as the proofs in the appendix reference the Wan et al. proofs heavily.  I could be convinced (and in fact it seems likely) that there are some non-trivial ideas here, but the paper would need to clearly explain what they are.

This lack of clarity in both the overall exposition and in particular for the articulation of the contribution is the main weakness of the paper.

clarity,_quality,_novelty_and_reproducibility: Overall the writing and structure of Sections 2-5 are quite muddled and don’t clearly lay out for the reader the structure and story of the exposition.  I give some low-level comments below, but I have two high-level issues:

1) The flow from 3-4-5 is unclear.  I think Section 3 is intended to just be an overview of the results, but this isn’t made explicit.  Then Section 4 starts talking about what sets things converge to and claims this is somehow relevant for the overall convergence, but as far as I can tell nowhere in this section is the relevant ever made clear.  It might help to move 5 before 4 since this at least outlines the overall proof structure and refers to why some of the results in 4 are useful.  Regardless, I think the introductory paragraphs to 3 and 4 need a substantial rewrite to help the reader understand what to expect and why.

2) The handling of the SMDP material is confusing.  I mention one rough transition below, but overall I can’t tell how important this is to the results.  The introduction just describes it as a “direct extension”, but it consumes more than half the preliminaries and the entirety of Section 4 is stated in the language of SMDPs.  Does this play a fundamental role?  Is it just so the more general version is available for the extension and all of 4 would look essentially the same for MDPs?  And how much of this analysis (particularly in 4) is new vs standard?

Small issues:

First paragraph: “The discount factor in the discounted objective has been observed to be deprecated” – needs a cite

Bartlett & Tewari 2009 doesn’t appear in the list of references

The definition of “communicating” is ambiguous regarding the order of quantification.  Does it require there exists a single policy which works for all pairs of states or for all pairs of states such a policy exists?

In the definition of weakly-communicating “closed” is used without definition and I’m assuming the missing word in “that are [] under every policy” is transient.

“shifting ... by any constant vector results in [another] solution”

There is an abrupt transition to “If the agent has a set of options” with no explanation of what an option is or why an agent might have a set of them.  Moving the definition of a SMDP up would help but not entirely solve the rough transition.

Before equation (4), Inter-option Differnential Q-learning needs a cite unless it is actually in Puterman.

summary_of_the_review: My scores are based on the current draft of the paper with is hard to follow and lacks specificity about the contribution.  I would be much more positively disposed to a substantial rewrite which successfully addresses these issues.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the performance of differential Q-learning and RVI Q-learning for average-reward weak-communicating MDP.  Main contribution: the authors show that with proper learning rates, the two algorithms converges to the optimal q function (or bias function) assuming that each state-action (state-option) are sufficiently visited.
strength_and_weaknesses: Strength: Compared to (Wan et. al., 2021a), the proposed analysis works for general weak-communicating MDPs.

Weakness: 
1) The assumptions are too strong to make the theoretical results significant. In particular, in Assumption 4 the authors assume a general coverage ratio for the offline dataset, while in related offline RL papers (e.g., Jin et. al.), it is sufficient to assume a coverage ratio with respect to a optimal policy.

2) The paper is not self-contained. For example, the full proof of Theorem 1 is not presented. I understand that the proof might be very similar to that in (Wan et. al.), but I still suggest the authors to present the full proof or the high-level ideas.

Reference: Is Pessimism Provably Efficient for Offline RL (Jin et. al.)
clarity,_quality,_novelty_and_reproducibility: Overall the paper is well written and easy to read. The related work is also well discussed.
summary_of_the_review: Currently, the paper does not reach the bar of ICLR in my opinion. My score is 3 and I am willing to increase the score if the author can prove under a weaker assumption. And it would also interesting to find the sufficient and necessary conditions for the trajectory $(S_t,A_t)$ $(t\geq 1)$ to make the two algorithms converge (assume that the learning rates are properly chosen).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the convergence of off-policy algorithms, which learn a policy that optimizes the average-reward rate using data generated by some other non-controlled policy, for weakly-communicating MDPs, the most general set of MDPs that allow for a learning algorithm that can find under experience a policy of optimal average reward rate. In these MDPs, policies may induce multiple recurrent classes, while some states are transient, while others are reachable from any other state within finite steps. The paper presents results that prove convergence for two learning algorithms, RVI Q-learning and Differential Q-learning, in such MDPs, in a more general setting than has been shown so far. 
strength_and_weaknesses: Strength:
Extension of convergence results under fewer assumptions.

Weakness:
Lack of empirical demonstration of performance gains.
clarity,_quality,_novelty_and_reproducibility: There are no empirical and demonstrative results to be reproduced.
summary_of_the_review: The achievement of the paper relies on two steps: first, showing that solution sets are non-empty, closed, bounded, and connected; then showing that 0 is the solution to the Bellman equation under rewards 0. Utilizing previous work by Borkar, the convergence results follows. The result goes beyond previous work in that those previous proofs required that all optimal policies induce unichains, which is not always the case in a weakly-communicating MDP. The results are theoretically sound. A discussion on the practical relevance and empirical performance would strengthen the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper established new convergence results for weakly communicating MDPS. Reviewers raised concerns about the assumptions and novelties. The AC agrees and recommends rejection.
justification_for_why_not_higher_score: There are concerns about the strong assumptions and novelties.
Decision: Reject