Technical Summary: On-line Learning in Tree MDPs by Treating Policies as Bandit Arms

1. Problem Definition

The paper addresses the problem of on-line learning in Tree Markov Decision Problems (T-MDPs). A T-MDP is defined as a finite-horizon MDP where the state transitions form a tree rooted at a starting state $s_1$. A defining characteristic of T-MDPs is that every state is reachable from $s_1$ through exactly one state-action trajectory.

These structures naturally arise as abstractions of extensive-form games with perfect recall played against stationary opponents. The specific learning goal is to find a best response to an unknown but stationary opponent through repeated game interactions. The agent does not know the transition probabilities $p$ but knows the reward function $r$. The agent interacts with the environment by playing complete episodes starting from $s_1$, observing trajectories, and selecting new policies for subsequent episodes.

The paper investigates this problem in two regimes:

1. PAC (Probably Approximately Correct): The goal is to output a policy $\pi$ such that $V(\pi) \geq V(\pi^*) - \epsilon$ with probability at least $1-\delta$, minimizing the number of episodes (sample complexity).
2. Regret Minimization: The goal is to minimize the cumulative regret $R_T = \sum_{t=1}^T (V(\pi^*) - \mathbb{E}[V(\pi_t)])$ over $T$ episodes.

2. Methodology

The core methodological innovation is treating each policy in the T-MDP as a bandit arm. While this approach is conceptually straightforward, the number of deterministic policies is exponential in the number of states ($|A|^{|S|}$), making a naive implementation computationally and memory-prohibitive.

To overcome this, the authors propose a framework where policies share data based on the tree structure of the MDP.

2.1 Value Decomposition

The authors establish that the value of any policy $\pi$, $V(\pi)$, can be expressed as a convex combination of terminal returns. Specifically, $V(\pi) = \sum_{\sigma \in X(\pi)} q(\sigma) \cdot \rho(\sigma)$, where:

• $X(\pi)$ is the set of terminal states consistent with policy $\pi$.
• $q(\sigma)$ is the probability of reaching terminal state $\sigma$ from $s_1$ under $\pi$.
• $\rho(\sigma)$ is the discounted cumulative reward along the path to $\sigma$.

Since the reward function is assumed known, $\rho(\sigma)$ is known. The learning problem reduces to estimating the transition probabilities $q(\sigma)$ for terminal states. Crucially, data for estimating $q(\sigma)$ can be gathered by playing any policy consistent with $\sigma$, not just $\sigma$ itself.

2.2 Confidence Bounds and Data Sharing

The paper introduces a novel confidence bound for $V(\pi)$ that leverages the shared data among policies.

• Counting Mechanism: For a terminal state $\sigma$, the algorithm tracks $n_t(\sigma)$, the number of episodes where the played policy was consistent with $\sigma$, and $n_t^+(\sigma)$, the number of times $\sigma$ was actually reached.
• Policy Count: For a policy $\pi$, the "play count" $n_t(\pi)$ is defined as $\min_{\sigma \in X(\pi)} n_t(\sigma)$. This represents the bottleneck data availability for evaluating $\pi$.
• Estimator: The empirical value $\hat{V}_t(\pi)$ is an unbiased estimator constructed from the empirical probabilities $\hat{q}_t(\sigma) = n_t^+(\sigma) / n_t(\sigma)$.

2.3 Theoretical Foundation: Negative Cylinder Dependence

A significant technical challenge is that the random variables used to estimate $V(\pi)$ (Bernoulli outcomes of reaching terminal states) are dependent because multiple policies may be played in the same episode.

• The authors prove that these variables exhibit Negative Cylinder Dependence (NCD).
• They introduce "twin variables" (independent Bernoulli variables with the same means) to bound the deviation of the dependent estimator.
• Using Bernstein's Inequality on these twin variables, they derive confidence bounds (UCB and LCB) that hold with high probability. This allows the application of bandit algorithms (Lucb and Ucb) to the exponential set of policies with only polynomial memory and computation per step.

2.4 Algorithms

The authors adapt two standard bandit algorithms:

1. Lucb-T: An adaptation of the Lucb algorithm for the PAC setting. It iteratively selects the policy with the highest value estimate and the policy with the highest Upper Confidence Bound (UCB) among the rest, playing them until they are separated by $\epsilon$.
2. Ucb-T: An adaptation of the Ucb algorithm for regret minimization. It selects the policy with the highest UCB in every episode.

Both algorithms utilize a procedure called PU (Policy with highest UCB) to efficiently compute the maximizing policy in $O(|S||A||k_{max}| + |\Sigma|)$ time, avoiding the need to enumerate all policies.

3. Key Contributions

1. Analytical Result: A new concentration inequality (Theorem 2) establishing confidence bounds for policy values in T-MDPs. This result handles the dependence among data shared by policies and may have broader applicability to learning in sequential tasks.
2. Algorithmic Design: Conceptually simple algorithms (Lucb-T and Ucb-T) that treat policies as bandit arms but exploit the tree structure for efficient implementation.
3. Theoretical Guarantees:
   • Sample Complexity (Theorem 9): An instance-dependent upper bound for Lucb-T that sums a "gap term" over terminal states ($\sum_{\sigma \in \Sigma} \frac{1}{(\Delta^\epsilon_\sigma)^2}$) rather than over policies.
   • Regret Bound (Theorem 10): An instance-dependent upper bound for Ucb-T, also summing over terminal states.
4. Empirical Validation: Implementation and testing on three imperfect-information games of varying scales: Kuhn Poker (small), Leduc Poker (medium), and Reconnaissance Blind Tic-Tac-Toe (RBT, large, with millions of states).

4. Results

• Scalability: The proposed algorithms consistently outperform available alternatives (such as vanilla Lucb, Bpi-Ucrl, Mdp-GapE, Mccfr, and Uct) as the problem size increases.
• Data Sharing Efficiency: On small problems (3-card Kuhn Poker), vanilla Lucb (no data sharing) is competitive. However, on larger variants (5-card Kuhn Poker, Leduc, RBT), the "tree" variants (Lucb-T, Ucb-T) significantly outperform non-sharing baselines, demonstrating the necessity of data sharing for scalability.
• RBT Performance: The algorithms successfully handle RBT, a game with up to $2 \times 10^7$ states, where other PAC algorithms (Bpi-Ucrl, Mdp-GapE) failed to perform well.
• Theory vs. Practice: The experiments highlight gaps between theoretical bounds and practical performance, particularly in the PAC setting where stopping times can be prohibitively large, suggesting that while the algorithms are theoretically sound, practical tuning is essential.

5. Significance and Claims

The paper claims that its primary contribution is the generalization of well-known bandit algorithms (Lucb and Ucb) to T-MDPs by treating policies as arms. The significance lies in:

• Overcoming Exponential Complexity: Demonstrating that one can achieve polynomial memory and computation complexity despite the exponential number of policies, by utilizing the tree structure to share data.
• Instance-Dependent Bounds: Providing theoretical guarantees that depend on the "gap" at terminal states rather than the total number of policies, offering a more refined analysis than worst-case bounds.
• Practical Applicability: Validating the approach on large-scale imperfect-information games (specifically RBT), which serve as a benchmark for the feasibility of learning best responses in complex sequential decision-making problems against fixed opponents.

The authors note that their assumption of a known reward function is reasonable for their motivating domain (imperfect-information games) but is a restriction compared to general MDPs where rewards may be unknown. They also acknowledge that while their bounds avoid dependence on state-visitation probabilities (which can be arbitrarily small in general MDPs), this is a specific advantage of the T-MDP structure and known rewards.