Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper extends the results of [1] to a dynamic setting. To do this, the authors first propose a new formulation - markov matching markets. This formulation can capture centralized matching problems that may arise in ride-sharing apps, for example. They propose a general framework that used optimistic value iteration + max-weight matching such that any RL algorithms can be incorporated for efficient online learning. They prove that this approach achieves sublinear regret under certain assumptions.

[1] Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I. and Steinhardt, J. (2021).   
Learning equilibria in matching markets from bandit feedback
strengths_and_weaknesses: **Strengths**:
1. This paper initiates the study on dynamic matching markets through tools from machine-learning. The application of this formulation is well motivated through the example of ridesharing platforms 
2. The markov matching market formulation is novel and their approach combines max-weight matching + RL. Their show that their proposed approach achieves sub-linear regret under certain assumptions. The results and formulation are a natural extension to [1] and their main novelty comes from addressing new challenges that are specific to dynamic matching markets such as propagation of error through the time steps and from complexities that arise from regret decomposition.
3. The paper is well-written and well organized. It's very clear and easy to read.

**Weakness**:
1. The evaluation seems limited - they only consider linear features. Perhaps this paper could .benefit a little from a limitations section.

[1] Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I. and Steinhardt, J. (2021).   
Learning equilibria in matching markets from bandit feedback
questions: N/A
limitations: There isn't a discussion of limitations in the paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a Markov matching market model, and it proposes a general framework that incorporates max-weight matching and RL algorithms for efficient online learning. This paper proves that the algorithms achieve sublunar regret under proper structural assumptions. 
strengths_and_weaknesses: Strengths: 
This paper studies an important matching market problem. It extends traditional online RL with a matching problem at each step and incorporates a transition between contexts into matching markets. The problem combines online RL and matching bandit. This paper provides a general analysis framework and shows that the proposed algorithm achieves sublinear regret under proper structural assumptions. 

Weaknesses: 
Despite the theoretical proof and contribution, the paper does not have an experiment to evaluate how the method works in practical scenarios and potentially compare with online RL and matching bandits, both of which are supposed to perform worse than this paper. Given that the paper is practically-motivated, and its contribution from the literature results from the practical “matching” problem and “dynamic transitions”, an empirical evaluation seems necessary to better ground the contribution to the literature. 

questions: 
This paper is out of my area of expertise; however, I find the Markov matching market problem it solves very interesting and important. I hope the paper can provide more intuitions on the technical results and assumptions to make it more accessible to the general technical audience. 

(1) Given that there is no empirical result, I wonder if the paper can provide some insights on what scenarios the method can outperform matching bandits and whether these scenarios are realistic in practice. 
(2) Please provide explanations/intuitions on Assumptions 5.1 and 5.2, why they are reasonable to make, and what they mean in practice. 
(3) What’s the complexity of the proposed meta-algorithm? Is this algorithm realistic to implement in practice? 
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers Markov Matching Markets consisting of three parties: two sides of agents (e.g. sellers and buyers) and a principal. They extend the setting of matching markets with bandit feedback to a problem where the principal, next to choosing the matching, determines context transitions (which are Markov). The authors address this problem treating it inside the RL/MDP framework. The algorithm Sequential Optimistic Matching is proposed and a sub-linear regret bound proven for the special case of linear function approximation. 
strengths_and_weaknesses: The problem considered in this paper is interesting and the chosen problem formulation intuitive and well-motivated. To the best of my knowledge, the work is novel and has not been studied in this form before. Moreover, the formulation of this dynamics matching problem as a RL problem is quite nice and informative. 
I also found the presentation in the first four sections exceptionally well done considering the amount of notation and concepts the paper is forced to introduce (except for some minor points, see below). 

I think that the paper would benefit from a more extensive discussion of the results. In particular, as only linear function approximation is discussed, additional comments on this would be helpful to include in the paper. I understand that the page limit made this difficult to add in the main paper. 

(Although I had a look into the proofs, I did not rigorously check for their correctness.) 
questions: To me it was not entirely clear how you obtain optimistic estimates of the utilities and also why the added bonuses in equation (12) are the right choice. Could you give an explanation/intuition of the chosen bonuses and how you obtain the optimistic estimates?  


Minor suggestions: 

1. Please define the norm $\lVert \cdot \rVert_{A}$, where $A$ is a matrix, somewhere in the text. The definition of this norm was not clear (to me) when it was first used in equation (12). (I also didn't find a definition in the appendix, but had to check in Abbasi-Yadkori et al.)

2. In Section 4.3, it would be helpful to state that the subroutines UE, RE, QE, OM are described in Section 5. Also writing the names out directly after first using the abbreviation would help (in particular for QE and OM). 

limitations: As mentioned above, I think that the paper would benefit from a more extensive discussion of the results and limitations. In particular, only the case of linear function approximation was analysed in the paper and additional comments on this would be helpful.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work frames a Markov matching market model and tackles it in a reinforcement learning (RL) framework. The model extends the previous works (e.g., [29]) to consider a dynamic scenario. Techniques from both RL (i.e., optimism) and market matching (i.e., max-weight matching) are connected to solve this problem. 

A general framework is first proposed, which nicely decomposes the problem into two sides (the planner and the agent) by introducing the pseudo-reward. Both sides depend on optimistic estimations of the user's utilities. The planner's problem becomes an RL one, where the rewards are not directly observed but are instead estimated by solving the stable matching with optimistic estimations (through an LP). The agent's problem boils down to finding a good matching with bandit feedback, which again is based on optimistic estimations. In the case of a linear model, sublinear regret bounds are proved.
strengths_and_weaknesses: - (S) This work connects the study of RL and economic problems (i.e., market matching), which is interesting. I believe this is a good attempt to benefit other fields from the recent advances in RL theory.
- (S) The design and analysis are sound and enlightening. Especially, techniques from RL and market matching are nicely combined.
- (S) The overall writing is clear under the page limits. Sufficient background knowledge of market matching is provided in the appendix (which benefits me a lot).
- (S) One especially interesting point in my view is the usage of the optimistic estimation of user utilities. It plays an important role on both sides of the problem. For the planner's side, these estimations ensure an optimistic version of pseudo-reward, which naturally provides the required optimism in RL learning (thus confidence bound is only added to the estimation of the transition in the linear model). For the agents' side, it naturally links the problem back to [29] to find good matching with bandit feedback.
- (W) As I am unfamiliar with the literature on market matching, the techniques are somewhat not exciting from the RL theory perspective. Especially, after decomposing the problem into two sides, the planner's side (Theorem 5.5) is similar to the standard RL setting (thus solved by similar techniques in [33]). The agents' side seems to closely follow [29] (while I am not familiar with it), especially from Theorem 5.4. Thus, the overall feeling about this work is adding a layer (i.e., the planner) to the market matching problem to handle the dynamic environment.
- (W) Following the previous point, I believe in general, a more clear statement of theoretical contributions (especially, insights) should be given to make the paper stronger given its theoretical nature.
- (W) The decomposition of the regret seems to heavily really on the assumption that only the actions of the planner affect the transition, while the selected matchings and transfers only affect reward in each step. I am not sure whether this is a reasonable assumption in economic literature. However, up to my understanding, it largely simplifies the scenario.
questions: 1. I have only skimmed through the proof, and it would be nice if the authors can highlight some key theoretical challenges in this work, especially compared to [33] (for the planner's side) and to [29] (for the agents' side).
2. It would be helpful if some clarifications (or practical motivations) can be given on why the transition does not depend on the selected matching and transfer, which seems critical for regret decomposition.
3. In Eqn. (6), I am wondering about the definition of $\mathcal{M}_h$. Does the illustration on line 203 mean that there are many myopic stable matchings and they lead to different rewards? It confuses me given Proposition B.2, which says the stable matching maximizes the reward.
limitations: See weakness.
review_title: null

Meta-review: metareview: This paper extends work on learning equilibria in matching markets from bandit feedback to more general Markov structure.  The paper brings to RL/MDP approaches to bear in this context.  An algorithm is presented and sublinear regret bound established.  This seems like a solid contribution and the reviewers are supportive of acceptance.
confidence: Certain
Decision: Accept