Source-linked AI summary
REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
Peter L. Bartlett, Ambuj Tewari
TL;DR
General MDPs do not admit regret guarantees under the stated criterion, so the paper studies weakly communicating MDPs and finite-time regret bounds. It introduces Regal, with a span-based regularization approach, and relates the optimal bias span to diameter-like quantities.
Problem
General MDPs cannot have regret guarantees under the stated criterion, motivating finite-time analysis on the restricted class of weakly communicating MDPs.
Method
Regal selects policies using regularization, and Algorithm 2 solves a constrained optimization problem when an upper bound H on the optimal bias span is known.
Results
The paper gives Regal regret guarantees for weakly communicating MDPs and proves sp(h⋆) ≤ Dow ≤ D when rewards lie in [0, 1].
Takeaways & Limitations
The optimal bias span sp(h⋆) can replace the larger diameter D in the related regret result, extending the result to weakly communicating MDPs.
Takeaways & Limitations
The theorem’s regularization parameters require unavailable pre-episode visit counts, while the implementable algorithm assumes a known upper bound H ≥ sp(h⋆(M)).
Abstract
from arXiv · showhide
We provide an algorithm that achieves the optimal regret rate in an unknown weakly communicating Markov Decision Process (MDP). The algorithm proceeds in episodes where, in each episode, it picks a policy using regularization based on the span of the optimal bias vector. For an MDP with S states and A actions whose optimal bias vector has span bounded by H, we show a regret bound of ~O(HSpAT). We also relate the span to various diameter-like quantities associated with the MDP, demonstrating how our results improve on previous regret bounds.
1 INTRODUCTION
The paper studies finite-time regret for learning in weakly communicating MDPs and introduces Regal, which regularizes optimistic planning using the span of the optimal bias vector.
- Problem setting: Regret measures the gap between the optimal per-step reward and the reward accumulated by a learning algorithm over T steps.Sublinear regret implies convergence of expected average reward to the optimal value.
- Problem setting: Weakly communicating MDPs allow states to be mutually reachable within one subset while all states in the other subset are transient under every policy.This subclass is considered because general MDPs may make optimally rewarding states unreachable from the starting state.
- Optimality structure: The optimal gain is state independent, and the optimal bias vector is defined only up to addition of a constant all-ones vector.The paper makes the dependence of the optimal gain and bias on the underlying MDP explicit.
- Contributions: Regal achieves a high-probability regret guarantee when started from any state of a weakly communicating MDP.The paper states this as the algorithm’s main contribution, with logarithmic factors hidden by the tilde notation.
- Regal: Regal selects an optimistic MDP from a confidence set by trading off high gain against low span through a regularized objective.The confidence set contains the true MDP with high probability.
- Relation to prior work: For rewards in [0, 1], the optimal bias span is no larger than the one-way diameter, which is no larger than the MDP diameter.This relation supports replacing the diameter in prior regret results with the smaller optimal-bias span.
2 PRELIMINARIES
The preliminaries assume known bounded rewards and unknown transition probabilities, then introduce the dynamic programming operator used to compute finite-horizon optimal values and express the optimality equations.
- Assumptions: The paper assumes rewards r(s, a) ∈ [0, 1] are known while transition probabilities are unknown.It states that estimating rewards would increase the regret bound only by a constant factor.
- Dynamic programming: The dynamic programming operator T is used to define the recursion V n+1 = T V n.V n(s) is the maximum expected reward obtainable in n steps from state s.
- Dynamic programming: The optimality equations can be written succinctly using the dynamic programming operator T.These equations characterize the state-independent optimal gain and associated bias structure.
3 REGAL
REGAL selects optimistic MDP policies using confidence sets and regularized average reward, then executes them in episodes. Its guarantees cover versions with known or unknown bounds on the optimal bias span.
- REGAL: REGAL estimates transition probabilities and builds a high-probability set M(t) containing the true MDP.The confidence set includes MDPs whose transition probabilities satisfy the specified confidence constraints.
- REGAL: Episodes end when a state-action pair reaches its episode visit threshold, after which REGAL starts the next episode.The algorithm uses counts Nk(s,a) and follows the selected policy until some pair has been visited Nk(s,a) times.
- REGAL: In each episode, REGAL chooses an MDP maximizing a regularized average optimal reward over the confidence set.The regularization parameter Ck is set at the start of episode k, and the associated policy is followed during the episode.
- REGAL: If H ≥ sp(h⋆(M)) is known, constrained optimization yields Algorithm 2 with a high-probability regret guarantee.The constrained optimization imposes sp(h⋆(M)) ≤ H while maximizing the optimal gain.
- REGAL: Regal.D removes the need to know an upper bound on sp(h⋆), using a doubling trick but obtaining a regret guarantee of ~O(sp(h⋆)S^3AT).The episode-length guess is doubled when incorrect; Theorem 3 provides the corresponding guarantee.
4 SPAN AND DIAMETER
The paper relates the optimal bias span to hitting-time and diameter quantities in weakly communicating MDPs. These relations show that diameter-based bounds can be loose while the span may remain substantially smaller.
- SPAN AND DIAMETER: For aperiodic weakly communicating MDPs, value iteration converges, and the limiting optimal values support span and hitting-time comparisons.The proof starts from value iteration and compares policies that reach one state before following an optimal finite-horizon policy.
- SPAN AND DIAMETER: Aperiodicity transformations extend the argument from aperiodic to periodic weakly communicating MDPs.The transformed MDP remains weakly communicating, and its quantities are related to those of the original MDP.
- SPAN AND DIAMETER: Both diameter inequalities can be arbitrarily loose in a two-state, two-action example.The example has sp(h⋆)=α/ϵ, Dow=1/ϵ, and D=∞.
5 LOWER BOUND
The lower-bound construction matches the upper bound except for its dependence on S, using weakly communicating MDPs in which identifying a slightly better action is statistically costly.
- Implications: The lower bound matches the upper bound except for the dependence on S.The authors compare this result with prior regret bounds for ergodic MDPs and conjecture tightness.
- Lower-bound theorem: Theorem 6 gives a lower bound for any algorithm on an MDP with Dow(M) ≤ dow, for any T > SA.The result applies to arbitrary S, A, dow, and starting state s.
- Construction: The construction uses S/2 copies of a two-state MDP, with one rewarding state and one slightly better action a⋆.Action a⋆ slightly increases the probability of remaining in the rewarding state.
- Construction: Each action must be probed at least cδ/ϵ^2 times to identify a⋆, creating the statistical difficulty underlying the lower bound.The reward difference between policies using and not using a⋆ exceeds ϵ.
- Parameter choice: Choosing α = 1/dow yields Dow = 1/α for the constructed MDP, while its diameter satisfies D = D2.The parameter choices also impose T > SA and ϵ < δ ≪ α.
6 ANALYSIS
The analysis decomposes regret across confidence-set episodes, controlling bad episodes probabilistically and bounding good-episode contributions through bias spans and episode lengths.
- Notation: The true MDP M is unknown, while λ⋆ and h⋆ denote its optimal gain and optimal bias vector throughout the analysis.The episode length is ℓk = Σs,a vk(s, a).
- Notation: The analysis tracks λk and h⋆k for the optimistic model Mk and distinguishes its transition matrices from those in M.The policies’ transition matrices are denoted by P̃k and Pk,j for the model and true MDP, respectively.
- Bias normalization: Normalizing bias vectors to minimum component zero makes the span equal to the infinity norm.Specifically, sp(h⋆) = ||h⋆||∞ under this normalization.
- Episode control: Auer et al.’s episode-count bound controls the number m of episodes up to time T, while bad episodes contribute only a small amount with high probability.Lemma 7 bounds m, and Lemma 8 controls episodes where the true MDP is not in Mk.
- Proof completion: Combining the regret bounds with the supporting lemmas completes the proofs of Theorems 1, 2, and 3.The final combinations are stated after the respective intermediate inequalities.
- REGAL episodes: REGAL, like UCRL2, operates in episodes and defines visit counts within each episode to support its regret decomposition.Its sub-episodes have geometrically increasing lengths, and Cauchy–Schwarz handles unknown visit counts.