PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning

Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, Ronald Ortner

arXiv:1802.04020v2cs.LGstat.ML

TL;DR

Regret bounds for exploration in weakly communicating MDPs can depend on diameter D even when the optimal bias span is much smaller. This paper develops SCOPT and integrates it into SCAL, reporting smaller regret than UCRL theoretically and empirically. It also notes that the general constrained optimization problem does not always have an established maximizer.

  • Problem

    Existing regret analysis emphasizes diameter D, although the optimal bias span can be much smaller and may be finite when D is infinite.

    Source: §1 · p. 1

  • Method

    The paper develops SCOPT for span-constrained planning and integrates it into a UCRL-like algorithm, SCAL, when an upper bound c on the optimal bias span is known.

    Source: §1 · p. 2, §6 · p. 6

  • Results

    SCAL achieves smaller regret than UCRL theoretically and empirically, and is presented as the first implementable approach inspired by REGAL.C.

    Source: §8 · p. 8

  • Takeaways & Limitations

    The paper concludes that an implementable algorithm can avoid scaling with diameter D in the stated setting when a finite bound on optimal bias span is known.

    Source: §8 · p. 8

    For the general constrained problem, existence of a maximizer remains open because gain may be discontinuous and the feasible set may not be closed.

    Source: §4 · p. 4

Abstract

from arXiv · show

We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound $c$ on the span of the optimal bias function is known. For an MDP with $S$ states, $A$ actions and $\Gamma \leq S$ possible next states, we prove a regret bound of $\widetilde{O}(c\sqrt{\Gamma SAT})$, which significantly improves over existing algorithms (e.g., UCRL and PSRL), whose regret scales linearly with the MDP diameter $D$. In fact, the optimal bias span is finite and often much smaller than $D$ (e.g., $D=\infty$ in non-communicating MDPs). A similar result was originally derived by Bartlett and Tewari (2009) for REGAL.C, for which no tractable algorithm is available. In this paper, we relax the optimization problem at the core of REGAL.C, we carefully analyze its properties, and we provide the first computationally efficient algorithm to solve it. Finally, we report numerical simulations supporting our theoretical findings and showing how SCAL significantly outperforms UCRL in MDPs with large diameter and small span.

1. Introduction

The paper argues that regret can depend on the optimal bias span rather than the MDP diameter, which may be much larger or even infinite. It builds on REGAL.C to present a tractable constrained planner and integrate it into SCAL.

1. Introduction

  • The paper focuses on regret, which compares an agent’s accumulated reward with that of an optimal policy during online learning.Source: §1 · p. 1
  • The optimal bias span can be much smaller than the diameter D and can remain finite in weakly communicating MDPs with infinite diameter.Source: §1 · p. 1
  • REGAL.C has span-dependent regret guarantees when c is known, but its constrained optimization lacks a computationally tractable solver.REGAL.D also requires solving a regularized problem for which no tractable algorithm is known.Source: §1 · p. 2
  • SCAL combines a computationally efficient constrained planner, SCOPT, with a UCRL-like learning scheme to obtain regret scaling with the bias-span bound c.The bound applies when an upper bound on the optimal bias span is available.Source: §1 · p. 2

2. Preliminaries

The preliminaries define the finite-MDP setting and the quantities used to analyze learning: gain, bias, bias span, diameter, and cumulative regret.

2. Preliminaries

  • The setup is a finite MDP with states, actions, reward distributions, and transition distributions, with S, A, and rmax known while rewards and transitions are learned online.Source: §2 · p. 2
  • A policy’s gain is its long-term average reward, while its bias function measures the expected accumulated difference from that stationary reward.For weakly communicating MDPs, an optimal policy has constant gain across states.Source: §2 · p. 2
  • Bias span is the range of a policy’s bias values, whereas diameter is the maximum minimum expected time to reach one state from another.The learning objective is cumulative regret against the optimal gain over T time steps.Source: §2 · p. 2

3. Optimistic Exploration-Exploitation

UCRL uses optimistic models and extended value iteration to choose policies episode by episode. The section then relaxes REGAL.C’s span-constrained optimization while preserving optimism and its regret guarantees.

3.1. Upper-Confidence Reinforcement Learning

  • UCRL builds high-probability confidence intervals for rewards and transitions, then uses extended value iteration to compute an optimistic policy for each episode.Its extended action space represents possible confidence-interval parameter values as fictitious actions.Source: §3.1 · pp. 2–3

3.2. A first relaxation of REGAL.C

  • REGAL.C constrains the bias span of plausible models, but its original search can be ill-posed or computationally intractable.The paper modifies the optimization problem and considers stationary constant-gain policies satisfying the span constraint, including randomized policies and models beyond the communicating subset.Source: §3.2 · p. 3
  • The relaxation preserves optimism over the same plausible MDP set, so an algorithm solving it retains REGAL.C’s regret guarantees.Source: §3.2 · p. 3
  • The paper proposes truncated value iteration to solve the relaxed problem and then integrate it into a UCRL-like scheme.Source: §3.2 · p. 4

4. The Optimization Problem

The optimization problem seeks a high-gain policy subject to a bias-span constraint, with constant gain needed for a well-defined objective. Its solutions may be randomized, and general existence of a maximizer remains open.

4. The Optimization Problem

  • The constrained optimization maximizes policy gain among randomized policies with constant gain and bias span at most c.Source: §4 · p. 4
  • For some MDPs and span bounds, a randomized policy can achieve greater constrained gain than any feasible deterministic policy.In the example, for 1/2 < c < 1, the randomized policy achieves gain c while the feasible deterministic policy achieves gain 1/2.Source: §4 · p. 4
  • Without restricting policies to constant gain, the constrained problem may have no dominating policy and its supremum may not be well defined.Source: §4 · p. 4
  • Whether the constant-gain constrained problem always admits a maximizer remains open because gain may be discontinuous and the feasible set may not be closed.For unichain MDPs, the feasible set is compact and gain is continuous.Source: §4 · p. 4

5. Planning with SCOPT

SCOPT adapts relative value iteration to enforce a bias-span constraint, then derives convergence and policy guarantees under stated contraction and feasibility conditions.

5.1. Span-constrained value and policy operators

  • SCOPT replaces the optimal Bellman operator in relative value iteration with a span-truncated operator and returns a constrained greedy policy when its stopping condition is met.The truncation guarantees the value vector has span at most c.Source: §5.1 · pp. 4–5
  • When the constrained operator is globally feasible, it yields the componentwise maximal value among decision rules whose one-step values satisfy the span constraint.The corresponding optimization can be formulated as a linear program.Source: §5.1 · p. 5

5.2. Convergence and Optimality Guarantees

  • If the optimal Bellman operator is a span contraction, the constrained operator preserves that contraction, giving SCOPT a fixed point and convergence from any initial vector.The fixed point defines a gain that upper-bounds the constrained optimization problem's supremum.Source: §5.2 · pp. 5–6
  • Under contraction and global-feasibility assumptions, SCOPT returns an ε-optimal policy; its fixed-point gain equals the constrained optimum when the associated policy is unichain.Without the unichain condition, the theorem guarantees only an upper bound on the constrained optimum.Source: §5.2 · p. 6
  • The fixed-point value has span at most c, but the associated policy need not be unichain, and a finite-iteration policy can have bias span larger than c.The regret analysis in the following section does not require the returned policy's bias span to satisfy the cap.Source: §5.2 · p. 6

6. Learning with SCAL

SCAL integrates SCOPT into a UCRL-like optimistic learning scheme for weakly communicating MDPs with a known bound on optimal bias span. Its regret can depend on that span rather than the MDP diameter, with a modification covering cases where the bound is large.

6. Learning with SCAL

  • SCAL applies SCOPT to a modified bounded-parameter MDP, where the modification supports the contraction and feasibility properties needed for the analysis.The method perturbs transition confidence intervals to make an attractive state reachable with nonzero probability from every state-action pair.Source: §6 · pp. 6–7
  • The modified problem is well defined, has a maximizer efficiently computable by SCOPT, and preserves optimism up to an accuracy of rmax/tk for constrained policies.This guarantee assumes the true MDP has optimal bias span at most c.Source: §6 · p. 7
  • For weakly communicating MDPs with sp{h*} ≤ c, Theorem 12 establishes a high-probability regret bound for SCAL.The supplied theorem passage does not include the bound's formula.Source: §6 · p. 7
  • When c ≤ rmaxD, SCAL's regret scales linearly with c, while UCRL's scales linearly with rmaxD, all other terms being equal.The gap between optimal bias span and diameter can be arbitrarily large; with infinite diameter, the passage contrasts SCAL's sublinear regret with UCRL's linear regret.Source: §6 · p. 7
  • When c > rmaxD, a parallel SCOPT-and-EVI variant chooses the policy with the smaller value span and obtains a regret scale involving min{max{rmax,c}, rmaxD}.If c is chosen below the true optimal bias span, the paper says it cannot prove a regret bound for that scenario.Source: §6 · p. 7

7. Numerical Experiments

The experiments show SCAL outperforming UCRL in a three-state domain where the optimal bias span stays small as the diameter grows, including when the diameter is infinite.

7. Numerical Experiments

  • At fixed horizon, UCRL regret grows linearly with diameter D, while the optimal bias span remains roughly 1.The domain has D ≈ 1/δ and bias span approximately 1.Source: §7 · pp. 7–8, Figure 4 · p. 8
  • In the experiments, SCOPT required neither extended-MDP perturbation nor its γ_k stopping adjustment.The authors set η_k = 0 and γ_k = 0 to speed up execution.Source: §7 · p. 7
  • SCAL always performs better than UCRL in the three-state domain, and smaller span constraint c yields lower regret.SCAL truncates the optimistic bias when s1 appears most rewarding, helping it discover that action a0 in s2 is suboptimal.Source: §7 · p. 8, Figure 5 · p. 8
  • With δ = 0, UCRL suffers linear regret while SCAL quickly recovers the optimal policy in the weakly communicating MDP with infinite diameter.The comparison is reported in Figure 5(b).Source: §7 · p. 8, Figure 5 · p. 8

8. Conclusion

The conclusion presents SCAL as an implementable, UCRL-like learner that uses a known bound on optimal bias span. The appendix index lists supporting proofs, SCOPT limitation analyses, and a larger-domain test.

8. Conclusion

  • SCAL uses SCOPT to exploit a known finite bound c on optimal bias span and achieves smaller regret than UCRL theoretically and empirically.The paper describes SCAL as the only implementable approach so far inspired by REGAL.C.Source: §8 · p. 8
  • Whether the assumption that c is known can be relaxed remains an open question.Source: §8 · p. 8

Index of the Appendix

  • The appendix index also flags SCOPT feasibility and convergence limitations and a test on the larger knight quest domain.It lists an LP interpretation of the policy associated with T_c^v and computation of that policy when T_c is feasible.Source: Index of the Appendix · p. 10
  • The appendix index lists proofs on SCOPT convergence, stopping conditions, approximation guarantees, and regret.It also lists proofs concerning perturbed and augmented extended MDPs.Source: Index of the Appendix · p. 10

A.1. Existence of gain optimal policies under bias-span constraint: the unichain case (proof of Lem. 4)

The appendix establishes existence of a gain-optimal policy under the bias-span constraint in the unichain case, discusses LP formulations for the constrained greedy policy, and illustrates limitations of SCOPT.

A.1. Existence of gain optimal policies under bias-span constraint: the unichain case (proof of Lem. 4)

  • In unichain MDPs, gain and bias vary continuously with stationary policies, making the constrained policy set compact and ensuring the maximum gain is attained.The proof uses continuity of the stationary distribution, reward, and bias; it assumes the constrained set is nonempty.Source: §A.1 · pp. 10–11

A.2. Greedy policy under bias span constraint: LP formulation

  • When D(c, v) is nonempty, the optimization defining T_c^v can be expressed as an LP, though T_c^v and its associated policy can be computed more directly.The objective is linear in the decision rule, with the span constraint expressed as linear constraints.Source: §A.2 · p. 11

B. Limitations of SCOPT

  • Examples show that T_c may be infeasible at a one-step application or fixed point, and its iterates may fail to converge even under stated policy conditions.The examples concern failure despite a nonempty constrained policy set and, for nonconvergence, unichain and aperiodic policies.Source: Figure 6 · p. 12, Figure 7 · p. 12, Figure 8 · p. 12

A.2. Greedy policy under bias span constraint: LP formulation

  • The usual primal LP approach fails for the general bias-span-constrained problem because the required properties do not generally hold and the span constraint is nonlinear in dual variables.Whether problem (7) admits an LP formulation remains open.Source: §A.2 · p. 12

B.1. Non-feasibility of Tc

The section shows that the constrained operator Tc can fail to represent feasible policies or converge, and describes how the policy construction and feasibility condition are characterized.

B.1. Non-feasibility of Tc

  • Tc may be globally infeasible at its fixed point even when Πc is nonempty, because it cannot converge to policies deterministic at maximal-bias states and stochastic below.Source: §B.1 · pp. 12–13
  • Duplicating actions with minimal rewards preserves Tc’s fixed point while making the operator globally feasible at vectors satisfying the span constraint.Source: §B.1 · p. 13

B.2. Non-convergence of T n

  • Even with unichain, aperiodic policies and a nonempty Πc, SCOPT’s stopping condition may never hold; Tc can cycle with period 2 instead of converging.Source: §B.2 · pp. 13–14

C. Policy δ+ v associated to Tcv

D.1. Feasibility of Tc (proof of Lemma 5)

  • Tc is globally feasible at v exactly when condition (10) holds in every state; when feasible, it equals the maximum over decision rules satisfying the span constraint.Source: §D.1 · p. 15

D.2. Contraction property of Tc (proof of Lemma 7)

The proof establishes that span truncation is a projection and that the resulting operator inherits span contraction, yielding convergence and approximation guarantees for SCOPT under stated conditions. It connects those guarantees to span constraints and a unichain policy, with the constrained and ordinary operators agreeing throughout iterations initialized with span at most c, supporting Theorem 10.

D.2. Contraction property of Tc (proof of Lemma 7)

  • Tc v ≤ Lv, and if sp{v} ≤ c and v ≤ Lv, then v ≤ Tc v.Tc is monotone, and its span non-expansiveness yields the contraction result when L is a γ-span contraction.Source: §D.2 · pp. 17–18
  • If L is a γ-span contraction, then Tc is also a γ-span contraction.Tc is the composition ΓcL, where Γc projects onto the set of value functions with span at most c.Source: §D.2 · pp. 15, 17, 18

D.3. Convergence properties of Tc (proof of Lemma 8)

  • Relative value iteration using Tc converges to a solution of the optimality equation, whose gain g+ is unique.The proof also establishes existence of a unique fixed point in the quotient space modulo constant vectors.Source: §D.3 · pp. 18–19

D.4. Approximation guarantees of SCOPT (proof of Theorem 10)

  • Under Assumptions 6 and 17, m_n e ≤ g_{π_n} ≤ M_n e; moreover, if π+ = (d+)∞ is unichain, g+ solves optimization problem (7).Source: §D.4 · p. 20
  • Under global feasibility and a unichain policy π+, the proof identifies g+ with gπ+ and hπ+ with h+ up to a constant, placing π+ in Πc.The argument uses span invariance under translation, Eq. 37, and the definition of Tc; it invokes Puterman (1994).Source: §D.4 · p. 21
  • If π+ is not unichain, its bias span may exceed sp{h+}, so π+ may fall outside Πc and the result may fail.Source: §D.4 · p. 21
  • When sp{v0} ≤ c, every iterate vn has span at most c, so Tcvn = Ncvn for n ≥ 1 and Theorem 10 follows under the stated assumptions.The proof also states that sp{h+} ≤ c, making Assumption 17 hold whenever Assumption 9 does; with Assumption 6, the first part of Theorem 18 follows.Source: §D.4 · p. 21

E. Modified bounded-parameter (extended) MDPs (Proof of Thm. 11)

This proof section develops modified bounded-parameter MDPs to establish Theorem 11, combining transition perturbations and reward augmentations while preserving key properties. It also bounds confidence-region failures and regret contributions from episodes where the true MDP is plausible, combining reward and transition bounds with support size Γ in the analysis.

E. Modified bounded-parameter (extended) MDPs (Proof of Thm. 11)

  • The η-perturbed transition model is unichain, and its optimal Bellman operator is a γ-span contraction with γ ≤ 1 − η < 1.The proof also bounds the difference between the original and perturbed Bellman operators by sp{v}η.Source: E. Modified bounded-parameter… · p. 24
  • Augmenting reward intervals from below leaves the optimal Bellman operators unchanged and preserves the clipped-operator equality.For vectors with span at most c, the stated lemma also equates the relevant policy sets in the original and augmented MDPs.Source: E. Modified bounded-parameter… · pp. 24–25
  • Combining the perturbation and augmentation makes Lemma 8 applicable to the modified operator, yielding a solution (g+, h+) to its equation.The proof invokes the contraction property and the unichain result for the combined MDP.Source: E. Modified bounded-parameter… · p. 25

F.2. Dealing with failing confidence regions

  • Theorem 22 bounds the probability that the true MDP is outside the plausible set Mk at time tk.The theorem applies for every episode k ≥ 1 and uses the confidence intervals in (48) and (49).Source: §F.2 · p. 28

F.3. Episodes whith M ∈Mk

  • When M ∈ Mk, the proof bounds the episode contribution using the SCOPT gain estimate and perturbation ηk = 1/(c√tk).The stopping criterion gives gain accuracy εk = 1/√tk; the analysis does not assume M belongs to the modified MDP set M‡k.Source: §F.3 · p. 29

F.4. Extended Value Iteration

  • When the convergence criterion holds, the recentered value vector wk has infinity norm at most c/2.The analysis uses the span feasibility of the value iterates under SCOPT.Source: §F.4 · pp. 29–30

F.5. Bounding the reward

  • For episodes with M ∈ Mk, the proof bounds the reward contribution using a martingale difference sequence and Azuma’s inequality.The reward bound is stated with probability at least 1 − δ/(20T^(5/4)).Source: §F.5 · pp. 30–31

F.6. Bounding the transition matrix

  • For episodes with M ∈ Mk, νk(ẽPk − I)wk splits into νk(ẽPk − bPk)wk and νk(bPk − Pk)wk; the difference concentrates, and νk(Pk − I)wk is an MDS.Source: §F.6 · pp. 31–32

F.7. Summing over episodes with M ∈Mk

  • For T ≥ SA, summing the episode-wise inequalities gives a final bound with probability at least 1 − 3δ/(20T^(5/4)).The derivation uses inequalities (54)–(56) in (53) and a union bound.Source: §F.7 · pp. 32, 34

F.8. Completing the regret bound

The appendix completes SCAL’s regret-bound analysis and reports additional figures, while the three-state section restates results from the main paper.

G.1. Three-States MDP

  • Figure 9 compares UCRL and SCAL behavior in the three-state MDP with δ = 0.005.Source: Figure 9 · p. 35

F.8. Completing the regret bound

  • SCAL’s final regret bound holds with probability at least 1−δ, and its second upper-bound term becomes negligible for sufficiently large T.The proof uses a union bound over possible values of T.Source: §F.8 · p. 35

G. Additional Experiments

  • The additional-experiments section presents clearer figures for the three-state domain and introduces the Knight Quest domain.The three-state subsection restates the main-paper results in larger figures.Source: G. Additional Experiments · p. 35, §G.1 · p. 35

G.2. Knight Quest

In Knight Quest, SCAL substantially outperforms UCRL, while the domain pairs a large diameter with a small optimal-bias span. The results are reported over a horizon of 4 · 10^8.

Knight Quest mechanics

  • Armor prevents death by the dragon but makes movement succeed with probability 0.5 and gold collection succeed with probability 0.01.Without armor, all actions are deterministic.Source: §G.2 · p. 37

Properties of the game

  • The game has S = 360 states, A = 8 actions, diameter D ≈ 250, and optimal-bias span sp{h*} ≈ 3.28.The large diameter comes from a path involving armor and one unit of gold, although the optimal strategy is to collect gold, buy the key, and rescue the princess.Source: §G.2 · p. 37

Motivation and interpretation

  • The authors attribute SCAL’s advantage to conditioning exploration on a small span, whereas UCRL explores remote states that appear promising despite being irrelevant to the goal.The domain’s large diameter arises from actions and paths that are orthogonal to the optimal rescue strategy.Source: §G.2 · p. 37

Results

  • The evaluation runs UCRL and SCAL with different span constraints for T = 4 · 10^8, using Bernstein’s bound and no transition-matrix perturbation for SCAL.The reported curves average 15 runs; the regret plot includes 95% confidence intervals.Source: §G.2 · p. 37, Figure 12 · p. 38
  • SCAL outperforms UCRL by a big margin in Knight Quest, where regret and optimistic-bias span are plotted against T.The curves show identifiable linear and logarithmic regret regimes, while the square-root regime is almost absent.Source: §G.2 · p. 37, Figure 12 · p. 38
Loading 1802.04020v2…