Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an extension of the existing Configurable-MDP framework to a non-cooperative setting; one where the agent and the configurator could also have different reward functions. This setting (referred to as Non-cooperative Configurable MDPs) allows for modelling a wider range of situations, which also include the scenario where the agent and configurator display non-cooperative behaviour. The problem-setting is modelled as a leader-follower game, with the configurator as the leader and the agent as the follower. The authors present two algorithms for the configurator: AfOCL- which assumes that during online interaction the configurator can observe the agent's actions; RfOCL- which assumes that during online interaction the configurator can observe the agent's actions and obtains noisy estimates of its reward as well. The authors go on to prove that AfOCL achieves finite expected regret, which scales *linearly* with the number of possible configurations. This is already an improvement over the standard UCB algorithm which yields a regret that grows indefinitely over time. They also show that RfOCL the regret does not depend on the number of configurations under the assumption that the agent has a non-zero probability in some time-step of the horizon to visit every state in the MDP. The experimental evaluations were carried out on two environments: A configurable gridworld, and a simulated teacher-student environment. In both settings, their algorithms obtain constant  cumulative regret, as opposed to the logarithmic regret suffered by the UCB algorithm, validating their result.
main_review: **Pros**

* The paper was very clearly written and all the terminology well explained before they were presented.
* The experimental setup was very clean, and the results presented provided insights into the workings of the 2 proposed algorithms. The fact that both stochastic and deterministic policies of the agent were considered, validates the performance of the algorithms in all settings.
* The claim in the paper is that the regret bounds presented are the first problem-dependent regret results for multi-entity MDPs. This result can be exploited in the multi-agent adversarial RL setting to design more robust policies.

**Cons**

* Experimental Evaluations: The evaluation on the 2 environments presents proof of concept necessary to validate the theoretical results. However, it would be interesting to empirically see the performance of the algorithms on a purely adversarial setting, and get some further insights into worst-case performance in such a setting. Maybe illustration of the algorithms on such a setting could be an interesting add-on.

**General Comments** Overall, the paper was well structured and the ideas were coherent. 

*Originality*: Novel

*Clarity*: Clear

*Quality*: Good

*Significance*: High

limitations_and_societal_impact: The paper explicitly states its limitations. As the paper mainly has theoretical results, it potentially has no negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors provide an algorithm for online learning in a non-cooperative configurable MDP. They propose a setting where a configurator can choose a transition model for the MDP from a finite set of models. The goal is then to observe the agent's behaviour (either the state-action sequences or a noisy reward) and to learn an optimal configuration that results in maximum configurator reward given that the agent behaves optimally with respect to its own reward function.  
main_review: The paper is written clearly. However, some of the notation and concepts can be a bit dense and a use of a toy example or two can greatly help readability of the paper. Additionally, I feel the problem is not sufficiently motivated. The examples provided in the introduction are all well studied applications with numerous approaches. The authors do not do enough to explain why their new approach is necessary compared to past work. 

As noted by the authors, the work in this paper is really similar to the multi-armed bandit formulation. However, the authors argue that in most bandit formulations, the regret is unbounded as they do not incorporate the agent's observed policy or reward into the algorithm as is done in this paper. While this is true, I don't know if the novelty in this paper is sufficient for a publication. As far as I can tell the approach is a relatively straightforward extension of using the observed actions or rewards of the agent to estimate the value function and choosing the corresponding best configuration. 

Overall, if the authors clarify the above point, I think the paper is interesting, and I believe has an incremental contribution to the literature. However, I believe it is not sufficiently well motivated and the contribution is not yet strong enough for publication. 

Response: I appreciate the authors' response and they addressed my issues with the multi-armed bandit and novelty. 



limitations_and_societal_impact: This work is mainly theoretical in nature and is unlikely to have an immediate social impact. However, the authors do provide some examples (such as a supermarket owner optimizing their shelves for profit) in which their work may be applied. It would be worth a small discussion to address if these applications for the work in this paper is actually a negative impact. For example, following on with the example provided in the introduction, is it a social good that we provide more methods for businesses to manipulate user behaviour to optimize their profits? Can this work be used in social network applications to increase user engagement by showing extremist or misleading content even if it is not the users' original intent?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies learning in configurable MDPs with two-agents, a reinforcement learning agent and a configurator that can modify the environment parameters. In contrast to prior work, the paper considers a setting in which the configurator and the agent can have misaligned objectives. The setting is formally modeled as a Stackelberg game, in which the configurator is the leader that  selects a transition model and the agent is the follower that plays the best response policy under this model. The goal is to design a learning algorithm for the leader with provable regret guarantees. The paper provides two learning algorithms for the configurator and formally analyzes their regret properties, which turn out to be better than those of a naive solution based on UCB1. The paper supports its theoretical claims using simulation-based experiments.  
main_review: Overall, I enjoyed reading this paper and I find its results interesting and relevant. On the other hand, some aspects of the paper could be improved, e.g., in terms of clarity, and additional justification for the modeling assumptions could be provided. More detailed comments are below. 

Novelty: The paper studies a novel problem setting, building on the work of [29,27]. The setting has a clear motivation and the paper provides a good overview of the related work.  That said, the setting seems to be similar to adversarial attacks. How does this work relate to adversarial attacks in RL (e.g., adversarial attacks on policies 'Huang et al. Adversarial attacks on neural network policies', policy poisoning attacks 'Ma et al., Policy poisoning in batch reinforcement learning and control', attacks on environment parameters (rewards/transitions) 'Rakhsha et al., Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning', etc.)? 

Quality: In my opinion, the results of this paper advance the work on configurable environments, and the reasoning behind them is clearly explained. However, there are a few points that could be discussed in more detail: 
- The setting of the paper restricts the leader (configurator) to choose from a finite set of transition models. I think the implications of this restriction are not clearly stated in the text. For example, would the hardness result of Letchford et al. 'Computing Optimal Strategies to Commit to in Stochastic Games' apply in a more general case that doesn't place this restriction?  
- In general, the setting is closely related to stochastic games. This connection is mentioned and partly discussed in Section 6, but it could be extended. For example, can we model this setting as a Stackelberg stochastic game (e.g., where the leader has an influence on transitions via its policy)? The paper highlights that it is the first to provide problem-dependent regret bounds in multi-agent RL. On the flip side, the setting of this paper seems more restrictive than stochastic games, which is a standard framework for multi-agent RL.   
- Some of the variable/factors in the regret bounds could be more thoroughly explained. For example, it seems that the values of $\rho$ in Eq. (3) or $\hat K$ can be quite large, which could make the corresponding factors in the regret bounds bounds 'impractical'. Some discussion on this would be useful.   

Clarity: The structure of the paper is good, but some parts could be improved in terms of clarity as they contain typos or are ambiguous. Some notable examples include:
- The equation in line 158, should $\mathcal A_{i}^{k,h}(s)$ be a set of actions containing $\pi(s)$? 
- The sentence in lines 188-187, why is the regret bound in (3) independent of \Delta_i?
- The sentence in lines 283-284, how does offline setting relate to controlling all of the agents?  

Significance: The paper provides two new learning algorithms for a configurable MDP setting and derives non-trivial regret bounds for them. These results are potentially relevant for other sub-areas of RL, including environment design and multi-agent RL. 

limitations_and_societal_impact: The checklist states that the limitations are addressed in Section 8 (conclusion), but the conclusion only summarizes the paper and provides one sentence description of a future work. Since this is a theory paper, a discussion about limitations could explain the limitations of the modeling assumptions. Potential negative societal impacts are also not discussed, but given the topic of the paper, I don't find this necessary.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an extension to the configurable MDP framework, which implicitly assumes a shared reward function by the acting agent and the configurator, to the non-cooperative case where the reward functions of the two agents may be different and unknown to the other. Modeling the problem as a leader follower game, the papers present two online regret-minimization algorithms based on a multi-armed bandit strategy to learn the best environment configuration under different conditions. In the first, the configurator has access only to observed state-action traces (AfOCL), and in the second the configurator additionally observes noisy reward signals (RfOCL). The core idea of the algorithms is to iteratively prune the space of "plausible policies" of the acting agent based on observed feedback to compute an increasingly accurate optimistic value function for each environmental configuration for the configurator at the start of each episode. The authors prove that both algorithms incur finite expected regret, and show that regret scales linearly in the number of configurations for AfOCL, and is independent of the number of configurations in the case of RfOCL. Finally, the authors provide empirical results of the performance of AfOCL and RfOCL against the baseline UCB1 in two experimental domains, a gridworld domain and a teacher-student domain. 
main_review: Primary Contributions:

(1) Formal extension of the Conf-MDP model to the non-cooperative case (NConf-MDP). 

(2) Formalization of the problem as a leader follower game under Stackelberg equilibrium criteria. 

(3) Two online regret-minimization algorithms, AfOCL and RfOCL.

(4) Proofs of bounded expected regret for both algorithms, the first linear in the number of configurations, the second independent of that.

(5) Experimental evaluations on two domains, a gridworld domain and a student-teacher domain, against the baseline UCB1.

Pros:

(1) Configurable MDPs are a recent addition to the community and well-motivated by many real-world problems. The non-cooperative setting considered in this paper is the natural extension of this framework and of interest to the community. 

(2) The overall structure was clear and the main ideas were well-explained.

(3) The algorithms presented in the paper are simple and easily understood, but are intelligent in their approach and use of existing insights in related areas of multi-armed bandits and stackelberg games.

(4) The authors provide rigorous theoretical guarantees on their algorithms, and the simulated results appear to match these results for the most part. 

(5) The algorithms perform well and significantly outperform the baseline, UCB1, in the experimental domains considered.

Cons:

(1) Discussion of certain areas in the related work is lacking. In particular, the paper would benefit from a more detailed discussion of [45] and the broader area of environment design/shaping as it is central to the problem considered in the paper. We suggest some additional related work:

 --- "Equi-Reward Utility Maximizing Design in Stochastic Environments." Keren et al. IJCAI 2017

 --- "Mitigating Negative Side Effects via Environment Shaping." Saisubramanian and Zilberstein. AAMAS 2021. 

(2) Page 5, paragraph on "Regret Guarantees". The authors claim that "either an (s, h) pair is visited with high probability, or it will impact only marginally on the performance". Something is unclear, or perhaps incorrect, about this statement. A deterministic policy in a stochastic domain could to impactful states being visited infrequently. For instance, a state (say at timestep 1), with a small probability of being reached but with an arbitrarily high negative reward (e.g. a dead-end). Perhaps there is room for clarification.

(3) Experiments are performed on very simple and small domains that are not entirely convincing.

Additional Comments:

- In figure 1, should "round" be "episode"?

- Is there any intuition to the term \overline{K} in Theorem 5.2? As presented, it is hard to interpret the RfOCL regret in a meaningful way. 
limitations_and_societal_impact: This work assumes that the act of reconfiguring the environment does not have a cost to either configurator or acting agent. As the motivating domains are real-world problems with humans, if the environment is reconfigured dozens or hundreds of time for a single acting agent, possibly diminishing the cumulative reward earned by the agent in some configurations, this assumption may be violated. This assumption is also made in regular Conf-MDPs, but is perhaps more critical in the non-cooperative case where the reconfigurations are not always benefiting the human. Perhaps the authors could touch on this more.
review_title: null

Meta-review: Overall, the reviewers are fairly positive on this paper, which offers a novel take on the “environment design” problem in the non-cooperative (but not full adversarial) Stackelberg-type setting, using the framework of configurable MDPs. This new formulation is rather interesting, the (problem-dependent) regret analysis and the empirical confirmation offered are also valuable (though the empirical setup is critiqued as rather simple). The author response alleviated some of the reviewers questions and concerns, especially with regard to the problem formulation and its motivation There reviewers make some useful suggestions for improving the clarity of the paper, and related work suggestions. These should be addressed by the authors in revision. 

Decision: Accept (Poster)