Motivated by the study of generalization in biological intelligence, we examine reinforcement learning (RL) in settings where there are information-theoretic constraints placed on the learner's ability to represent a behavioral policy. We first show that the problem of optimizing expected utility within capacity-limited learning agents maps naturally to the mathematical field of rate-distortion (RD) theory. Applying the RD framework to the RL setting, we develop a new online RL algorithm, Capacity-Limited Actor-Critic, that learns a policy that optimizes a tradeoff between utility maximization and information processing costs. Using this algorithm in a 2D gridworld environment, we demonstrate two novel empirical results. First, at high information rates (high channel capacity), the algorithm achieves faster learning and discovers better policies compared to the standard tabular actor-critic algorithm. Second, we demonstrate that agents with capacitylimited policy representations avoid 'overfitting' and exhibit superior transfer to modified environments, compared to policies learned by agents with unlimited information processing resources. Our work provides a principled framework for the development of computationally rational RL agents.
(score raised from 6 to 7 after the rebuttal)
The paper explores the application of the rate-distortion framework to policy learning in the reinforcement learning setting. In particular, a policy that maps from states to actions is considered an information theoretic channel of limited capacity. This viewpoint provides an interesting angle which allows modeling/learning of (computationally) bounded-rational policies. While capacity-limitation might intuitively seem to be a disadvantage, intriguing arguments (based on solid theoretical foundations, rooted in first principles) can be made in favor of capacity-limited systems. Two of the main-arguments are that capacity-limited policies should be faster to learn and be more robust, i.e. generalize better. After thoroughly introducing these arguments on a less formal level and putting them into perspective with regard to reinforcement learning and related work in the literature, the paper demonstrates these properties in a toy grid-world example. When compared against a vanilla actor-critic (AC) algorithm, the capacity-limited version is shown to converge faster and reach better final policies. The paper then extends the basic version of the algorithm, which requires knowledge of the optimal value function, towards simultaneously learning the value function. While any theoretical guarantees are lost, the empirical results are still in line with the theoretical benefits, outperforming vanilla AC and producing better results in previously unencountered variations of the grid-world environment.
The paper is very well written and the toy-examples illustrate the theoretical advantages in a very nice and intuitively understandable way. The topic of modeling capacity-limited RL agents and exploring how capacity-limitation is an advantage, rather than a “bug” is very timely and important. In particular, rate-distortion theory might provide key-insights into building agents that generalize well, which is among the major open problems in reinforcement learning. The paper is thus very timely and highly relevant to a broad audience. 
The main weakness of the paper is that it is of quite limited novelty and that the brute-force approach towards using Blahut-Arimoto in RL is unlikely to scale to large, complex state-/action-spaces without major additional work. Continuous state-/action-spaces are in principle covered by the theory, but they come with additional caveats and subtleties (I appreciate the authors using discrete notation with sums instead of integrals). Additionally, when simultaneously learning the value function (in the online setting), any guarantees about Blahut-Arimoto convergence are lost. However, solving either of these issues is hard and many attempts have been made in the communications community. Despite these weaknesses I argue for accepting and presenting the paper at the conference for the following reasons: 
- modelling capacity-limited agents via ideas from rate-distortion theory (which is very closely related to free-energy optimization, such as ELBO maximization, Bayesian inference and the MDL principle) is an underrated topic in reinforcement learning. On a conceptual level, the strong idea is that moving away from strict optimization and infinite-capacity systems is not a shortcoming but can actually help building agents that perform better and generalize better. This is not a well established idea in the community. The paper does a good job at introducing the general idea, illustrating it intuitively with toy examples and pointing out relevant literature.
- Simultaneously learning the value function is necessary in the RL setting, but breaks quite a bit of the theory. However, very similar ideas seem to work quite well empirically in other settings, such as for instance ELBO maximization in VAEs, where the “value function” is the log-likelihood (under the decoder), which is learned simultaneously while learning a “policy” (the encoder) under capacity limitation (the KL term). Similar arguments can be made for modern InfoBottleneck-style objectives in deep learning. Based on this empirical observation, it is not unlikely that simultaneous learning of the value function works reasonably well without catastrophically collapsing in other settings and tasks. 
- While achieving a solution that strictly lies on the rate-distortion curve might be crucial in communications, it might be of lesser significance for building RL agents that generalize well - slight sub-optimalities (solutions that lie off the RD curve) should still yield interesting agents. Therefore, losing theoretical guarantees might be less severe for simply exploring how much the idea can be scaled up empirically.
Minor issues:
1) While the paper, strictly speaking, introduces a novel algorithm and the Bellman loss function (which requires knowledge of the optimal value function), I think that the main contribution is a clear and well-focused introduction of rate-distortion theory in the context of RL, including very illustrative toy examples. I do consider this an important contribution.
2) Transfer to novel environments. The final example (Fig. 4) does show that the capacity limited agent performs better in novel environments. However, I’m not entirely convinced that this demonstrates “superior transfer to novel environments” (from the abstract). While the latter might very well arise from capacity-limitations, I think that in the example in the paper there is not too much transfer going on, but the capacity-limited agent simply has a more stochastic policy which helps if unknown walls are in the way. After all, the average accumulated reward of the capacity limited agent does also decrease significantly in the novel environment - it simply does a slightly better random walk than the AC (correct me if I’m wrong, of course). On page 7, last paragraph this is phrased as: “agents retain knowledge of exploratory actions”. In my opinion this wording is a bit too strong to simply describe increased stochasticity.
3) Since the paper does provide a good overview over the literature, I think it would help to mention that the current main approach towards generalizing (deep) RL is via hierarchical RL (options framework, etc) and provide a good reference.
4) At the very end of the intro you might also want to mention that rate-distortion has been used before in the context of decision-making (not RL), for instance under the term rational inattention.
5) Page 5, last paragraph: the paper mentions that one Blahut-Arimoto iteration is enough. This is an empirical observation, justified by the toy experiments. However, the wording sounds like this is a generally known fact. Please rephrase to emphasize that this must not necessarily hold true in general and that convergence behavior might crucially depend on this.
6) It would be good to give readers some guidance towards choosing beta if doing an exhaustive grid-search is infeasible. I am aware that there is no good general rule or recipe, but perhaps something can be added to the discussion (even if it is just mentioning that there is no good heuristic, etc. - however, there should be plenty of research in communications that deals with estimating the RD curve from as few points as possible). 
7) Please consider adding this reference - it has a very similar objective function (but for navigating towards multiple goals) and is very much in line with some of the theoretical arguments.
Informational Constraints-Driven Organization in Goal-Directed Behavior - Van Dijk, Polani, 2013.