Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies an RL problem, where the rewards are given as a vector at each time step. The goal is to find a policy that balances the total rewards on different dimensions of the reward vector, i.e., one that maximizes the total reward of the worst dimension. More specifically, the paper takes an ex-post perspective and presents an online algorithm that achieves near optimality. An offline variant of this online algorithm is also proposed to alleviate the heavy cost of online computation in some applications. The authors also conducted experiments to evaluate the proposed algorithms.
main_review: **Strength:** The problem studied is interesting and well-motivated. The paper also clearly illustrated the difference between ex-ante and ex-post optimizations. The main algorithm presented has a theoretical regret bound. The paper is clearly written overall.

**Weakness:** The main techniques seem to rely on the work of Zahavy et al. (Reward is Enough for Convex MDPs), especially the generalization to concave minimization. Hence, the work looks somewhat incremental from a technical point of view. The authors may want to stress the difference between their work and that of Zahavy et al in the paper and highlight the original contribution. That said, the application of these techniques to the maximin problem is still very interesting.   

There is one technical question, which might be critical and I hope the authors could clarify: I do not see how Aogrithm 1 avoids getting stuck in a sink state that is undesirable for some reward types. For example, in Figure 1, if there is an additional state $s'$, connected by an arc from $s^o$ and with a self loop generating the same rewards as the self loop at $s^l$; nevertheless, from $s'$ no other states can be reached. In this case, a policy that always seeks to transit to $s'$ and loops there indefinitely is also optimal w.r.t. the second dimension of the reward. Therefore, the oracle $\Lambda$ may well pick this policy in the first episode, but if this is the case, the agent would loop at $s'$ in the subsequent episodes, obtaining reward $0$ for the first dimension. I wonder how the regret could diminish in this case? Is some assumption of ergodicity relevant here? I don't find any in the paper though. 

**Minor comments and suggestions:**

A typo: Right above Section 4: "...allows does not require..."

The figures in the experiment section could be arranged in a better way. They all look overly wide, and those in Figure 5 too small to read. If the space is a concern, I'd sugget putting Figures 3 and 4 side by side to save space for Figure 5.
summary_of_the_review: The ex-post maximin fairness problem is interesting and well-motivated. The authors made an effort to develop an algorithm to solve the problem, which looks somewhat incremental from a technical point of view given an existing result by Zahavy et al. (Reward is Enough for Convex MDPs). There is a potential technical issue (see Main Review) which I hope the authors could clarify.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers RL problem with a vectorial reward of $K$ dimension. The authors consider to maximize the minimal value function $\mathbb{E}[g_{min}(\bar{V}_{1:T})]$ and achieve a regret bound of $O(\sqrt{logK}T^{\frac{2}{3}})$ given an oracle to solve the RL problem with scalar reward. The authors also discuss the offline variant of the proposed algorithm. Finally, the authors verify their algorithm with a queuing system.
main_review: Strengths:
1. The authors provide both theorectical analysis and empirical experiments. In the analysis, they use multiplicative weight update to ensure the max-min fairness. In the numerical experiments, the proposed algorithm outperforms previous algorithms significantly.


Weaknesses:
1. The intuition of ex-post max-min fairness is not clear. The authors try to show difference between ex-ante max-min fairness and ex-post max-min fairness. However, the two problems are almost the same for weak communicating MDPs. In weak communicating MDPs,  for any policy $\pi$, by running $\pi$ for $T$ steps, $||\bar{V}_{1:T}-E[\bar{V}^{\pi}]||$ is bounded by $\tilde{O}(K\sqrt{D/T})$ with high probability, where $V^{\pi}$ is the expected average reward of $\pi$ and $D$ is the diameter. The proposed counter example is a non-communicating MDP, which is less important in both theorectical analysis and practical problems (in general, we deal with non-communicating MDPs by dividing it into several weak communicating parts).

2. The requirement of the proposed algorithm is too strong. Online-ReOpt needs to take an oracle to compute a near-optimal policy for any  scalar reward as a subrountine. In general, by online learning it cost $O(SAD/\epsilon^2)$ to learn an $\epsilon$-optimal policy in the worst case. Although it is possible to add a subroutine to learn such a policy, it would worse the final regret considering the current regret bound is quite poor.
summary_of_the_review: Overall the paper is well written and easy to read. However, given the concerns above, I tend to reject it.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the ex-post max-min objective for the vector reward RL problem. The paper provides a simple example to illustrate the difference between ex-ante and ex-post objectives. An MWU-based algorithm is proposed to solve the problem with a provable regret guarantee, where the algorithm resorts to an approximately optimal policy oracle episodically. The algorithm also features a variant that can fully rely on offline solutions. Numerical experiments on a classic queue control problem demonstrate the performance of the algorithm against two existing benchmarks. 
main_review: First, the paper is well-written and I really enjoy reading the work. 
The paper proposes a new objective and an asymptotic optimal algorithm. The presentation is clear and intuitive, and the analysis is also very clean. 

I mainly have two concerns:
(i) The motivation for the ex-post objective: The paper provides an example (Section 3.2) to illustrate the difference between ex-post and ex-ante policies. I like the example, but I still don't feel convinced about the necessity of the ex-post objective. Say, if we adopt a linear objective with equal weight or a CVaR objective to the two rewards for this example, would we end up with the same optimal policy as the ex-post? I think it would be great if the author(s) can construct an example, for which the optimal policy of the ex-post objective cannot be recovered by other existing objective functions, like the linear, ex-ante, CVaR, etc. In this sense, it means the ex-post objective provides us with a different class of risk-sensitive/fair policies.
Also, from a practical perspective, the numerical experiments should compare the time spent by the two classes of customers in the system, rather than the waiting time for each of the four queues. For instance, customer type 1 may care more about the sum of (rather than each of) the waiting times before Queue 1 and Queue 2. And for fairness purposes, we might want to max-min {Q1 Waiting + Q2 Waiting, Q3 Waiting + Q4 Waiting}. I am not sure if this would complicate the problem setup significantly. Please correct me if I misunderstood the setup here. 

(ii) Knowledge of the underlying dynamics (reward and transition): The oracle used by the algorithm requires the knowledge of the underlying reward and transition, at least some estimates of them. Strictly speaking, due to this requirement, I wouldn't call the setup of the paper "RL" but more of an MDP or stochastic dynamic programming. It seems to me that this requirement is necessary for both the algorithm and the analysis. I wonder whether asymptotic optimality can still be obtained if we don't have this knowledge. For example, if we replace the true probabilities/rewards in the oracle as their empirical estimates based on the samples observed so far in the online algorithm, my hunch is that the performance guarantee will no longer hold. 
summary_of_the_review: Overall, as mentioned above, I think the paper is very elegant. I would look forward to hearing the author(s) comments on my two concerns above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers ex-post max-min fairness, where an RL algorithm is provided with provable guarantees. The difference between ex-ante and ex-post are explained. 
main_review: 1. Some important related papers need reference: https://arxiv.org/pdf/1909.02940.pdf which seems to solve similar problem. 
2. Note that even though the E[min] and min(E) are shown to be different in an example, the gap is O(1/T), and not really relevant to the problem of regret. Thus, I believe that the algorithm of ex-ante will give the ex-post result with similar regret. 
3. Based on the above, it is unclear why the above paper approach where MDP is estimated using Dirichlet/optimistic sampling and a model based optimization is applied do not work in this setup? As T goes large, E[min] and min(E) will be similar and have gap of O(1/\sqrt{T}) and can be quantified giving an additional regret term, but other than that, most analysis will be re-used. 
4. The novelty in the approach needs better discussions. 
5. The regret bounds are sub-optimal. Given that oracle for linear reward problem will have \beta = 1/2, the regret is T^{5/6} which is very large when the model-based algorithms can achieve T^{1/2}. 
summary_of_the_review: The key issue in the paper is the in-efficient regret bound, and the approach novelty needs better explanations.
review_title: null

Meta-review: This paper studies an RL problem with vector rewards, where the goal is to maximize the expected minimum total reward (ex-post max-min fairness). This is different from prior works on a similar topic, where the goal is to maximize the minimum expected total reward (ex-ante max-min fairness). The authors propose an algorithm for solving the problem with $O(T^{2 / 3})$ regret and evaluate it.

This paper received two borderline reject and two reject reviews. The reviewers recognize the novelty of the objective. However, they are also concerned with its motivation and that the proposed algorithm relies on strong assumptions, such as that the used oracle knows the underlying reward and transition models, or at least has some estimate of them. At the end, the scores of this paper are not good enough for acceptance. Therefore, it is rejected.
Decision: Reject