Summary and Contributions: This paper introduces a version of Zap Q-learning that can be applied to arbitrary approximation architectures for Q-functions. Convergence analysis is undertaken, and a version of the algorithm with MLP function approximators is applied to several classical control tasks. POST-REBUTTAL ------------------------ I thank the authors for their response. I appreciate the comments around reorganisation of material, and clarification of some of the technical points I raised. There are two main concerns that I have with the paper that prevent me from strongly recommending acceptance, described below.

The reviewers are generally supportive of the paper. They have provided some very useful feedback, and I highly encourage the authors to incorporate that feedback. Primarily, it would be ideal to complete the paper reorganization as discussed, explain the limitations in the assumption on boundedness of the iterates, provide a toy example where the boundness assumption is not on its own enough to prevent divergence of Q-learning (i.e, even under that assumption, Q-learning diverges but Zap-Q does not) and finally to sweep over the parameters in the empirical comparison (even if that means the outcome is less positive for Zap-Q).

Additional Feedback: This paper addresses the problem of an RL agent that receives additional observations, after executing every action, which provide it with information about possible transitions that it could have experienced. These side observations might be generated, for instance, by auxiliary sensors. The authors formalize this setting by can defining a feedback graph based on the additional observations. Feedback graphs may be used by model-based RL algorithms to learn more efficiently. In particular, the authors show that the regret of the resulting model-based algorithm is bounded by certain properties of the graph, instead of depending on the number of states and actions that exist in the original problem (without side observations).

All reviewers have positive opinions of this paper, with scores of (7, 7, 6, 6). I also agree that the paper is quite novel and intriguing. The main issue appears to be readability, particularly regarding the extremely lengthy supplemental material. Quoting from the reviewers: This is a well-written theoretical paper. Although it does not demonstrate empirically that feedback graphs work in real-life problems, the underlying theory seems sound and the formal results that are presented are certainly not trivial.

We study the problem of multi-agent reinforcement learning (multi-agent RL) with differential privacy (DP) constraints. This is well-motivated by various real-world applications involving sensitive data, where it is critical to protect users' private information. We first extend the definitions of Joint DP (JDP) and Local DP (LDP) to two-player zero-sum episodic Markov Games, where both definitions ensure trajectory-wise privacy protection. Then we design a provably efficient algorithm based on optimistic Nash value iteration and privatization of Bernstein-type bonuses. The algorithm is able to satisfy JDP and LDP requirements when instantiated with appropriate privacy mechanisms.

Strengths: This work extends the KG-A2C agent in several ways: First it uses attention to re-weight the different components of textual observations (e.g. The output of this first attention is then combined with another attention computed over multiple different sub-knowledge graphs corresponding to the connectivity of locations, objects in the current location, inventory, and anything that is connected to the current player. While none of the individual building blocks are particularly novel, the combination of all of these elements introduces a lot of flexibility to structurally decompose the different types of knowledge available in the game and allow the agent to pay attention to specific subsets of this knowledge. This flexibility pays dividends when it comes to the experimental evaluation and where this agent significantly improves on KG-A2C in nearly every game. The ablations presented validate that the full stacked architecture is indeed needed to maintain current levels of performance, and the analysis shows that the attention mechansims are working well insofar as they distribute attention correctly between locations descriptions and inventory contents as needed to generate the action.

The work is an interesting approach of extending KG-A2C with sub-graphs to achieve impressive state of the art performance on several games. Ablation studies show that this architecture is needed to achieve the performance and the attention analysis is interesting. The work could benefit from a more thorough analysis of what the model is doing (beyond just attention values which are questionable). The paper could also benefit from improved clarity in its writing.

Reinforcement learning (RL) algorithms are typically based on optimizing a Markov Decision Process (MDP) using the optimal Bellman equation. Recent studies have revealed that focusing the optimization of Bellman equations solely on in-sample actions tends to result in more stable optimization, especially in the presence of function approximation. Upon on these findings, in this paper, we propose an Empirical MDP Iteration (EMIT) framework. For each of these empirical MDPs, it learns an estimated Q-function denoted as \widehat{Q} . The key strength is that by restricting the Bellman update to in-sample bootstrapping, each empirical MDP converges to a unique optimal \widehat{Q} function.

Goal-conditioned reinforcement learning is a powerful way to control an AI agent's behavior at runtime. That said, popular goal representations, e.g., target states or natural language, are either limited to Markovian tasks or rely on ambiguous task semantics. We propose representing temporal goals using compositions of deterministic finite automata (cDFAs) and use cDFAs to guide RL agents. On the other hand, cDFAs form a countably infinite concept class with Boolean semantics, and subtle changes to the automaton can result in very different tasks, making them difficult to condition agent behavior on. To address this, we observe that all paths through a DFA correspond to a series of reach-avoid tasks and propose pre-training graph neural network embeddings on "reach-avoid derived" DFAs.

Weaknesses: The first essential issue in LICA algorithm is that the definition of the centralized value-function is not clear. In particular, what exactly is the proposed value function is trying to approximate? During training, this centralized value function is trained conditioned on a sampled joint action (Eq.3), while during policy updating, it is used in a way that conditions on the concatenation of the probability over actions output by each agent's policy. Due to this inconsistency in the input of the value-function, this critic should not be able to provide a correct value-estimation for the stochastic policies when calculating the policy gradient. The paper should give a further explanation and theoretical analysis of this approach.