Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning

Summary

The work is interested in answering the following question: "In the RL setting, can we identify the best policy faster if we only estimate the difference between the value of individual policies?". The paper provides a positive answer in the contextual bandit setting and a negative, but more nuanced answer for tabular RL. Exploiting the difference between value estimates of a reference policy and target policies, the authors propose an algorithm that achieves a better sample complexity than the best one in the literature so far, while matching the sample complexity achieved for contextual bandit in special settings.

Strengths

- **Relevant Problem**: The question of reaching the optimal sample complexity of identifying the best policy (with high probability) is an important theoretical question that can have a big practical impact. - **Novel, important results**: The authors analyse the $(\epsilon, \delta)$-PAC policy identification for tabular RL, give valuable insight about the problem and derive an algorithm that improves on the best sample complexity obtained so far. - **The paper is beautifully written**: I genuinely enjoyed reading the first two sections. The authors do a magnificent job at introducing the problem and position their contribution in the literature. The next sections get more technical but they are still pleasant to read. The authors invest in sharing their intuition with the reader to alleviate the technical difficulties. The paper is well structured, and helps you understand the thought process of the authors which is highly appreciated.

Weaknesses

- **The proposed algorithm is complex to implement**: As pointed out by the authors, enumerating all policies from $\Pi$ can make the algorithm impractical. This narrows the applicability of the algorithm to simple problems even if I understand that the primary goal of the paper is of a theoretical nature.

Questions

- In an A/B test scenario, we have only two policies that are compared. How does the PERP algorithm improve on naively looking at the difference (or relative difference) of the estimated value of A and B? - Intuitively, what makes the tabular RL way more difficult than the bandit setting? Can it be alleviated by adding more structure? Do we have the same guarantees for contextual bandit, with say, a linear assumption? - The PERP algorithm is complex and encapsulates other algorithms in the inner loop. Is there a way to reduce the complexity of the algorithm and come up with a more practical variant even if we lose some of the guarantees?

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

N/A.

Summary

The author investigate if estimating the difference in policies is sufficient in determining the best policy for contexual bandits and tabular RL. A (somewhat) practical algorithm is proposed to determine the number of samples needed without any unknown quantities.

Strengths

- The motivating example clearly explained the difference between estimating policy values directly vs their difference - Identifying the when $\rho_\Pi$ is sufficient in determining the optimal policy in is novel - Limitations of the algorithm is clear

Weaknesses

- Some intuition could have been provided to describe certain value such as $U(\pi, \bar{\pi})$ or $\hat{\delta}^\pi_h$ to make the resulting bounds easier to interpret. - In section 4.2, it is difficult to see why the difference estimate has reduced variance

Questions

- In Lemma 1, what is the difference when $E^M[\tau]$ when compared to $E[\tau]$ on line 182? - Could an example be provided of an MDP with Action-Independent Transitions. It's unclear to me how a sub-optimal policy can exist in this setting.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

4

Limitations

No concerns.

Summary

This paper studies the problem in tabular RL: finding an \epislon-optimal policy given a set of policy with high probability. The author proposed with a new lower-bound of this problem and explained why the previous one is not correct with an example. The author proposed one algorithm PERP that computes reference policy, measures the difference between policies, and refines policy set through episodes. The author provided sample complexity analysis.

Strengths

This paper is well presented. The idea is conveyed clearly. The paper proposes a new lower bound and provide one example that is easy to understand. The explanation of algorithm is clear.

Weaknesses

The paper didn't provide the computational complexity of the algorithm. It would be better to mention the computational complexity by the end of the section describing algorithm.

Questions

How the sample complexity change when abitrary choosing a reference policy? The U(\pi, \bar{\pi}) should be upper bounded by a constant value, if I could arbitrary choose a reference policy, does it mean that I sacrifice sample complexity for computational complexity? If so, how much? Since it seems costly computationally when I iterate through the whole policy set to find a reference policy but the sample complexity won't decrease much. Please correct me, thanks.

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The authors have confronted the limitations in section 7.