Asymptotically optimal regret in communicating Markov decision processes

Victor Boone

REVIEW 2 major objections 4 minor 11 references

Asymptotically optimal regret in communicating Markov decision processes

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that an algorithm, ECoE*, attains the lower-bound regret rate $K(M)\log T + o(\log T)$ for every communicating Markov decision process in a Bernoulli-reward, strongly product-form class, making the lower-bound constant…

desk verdict A serious and inventive attack on a central open problem in average-reward RL, but the stated regularization schedule (18) violates the paper's own Assumption 6(A5), so Theorem 7 is not proven as written. read the letter →

arxiv 2505.18064 v1 pith:3X2JTKJS submitted 2025-05-23 cs.LG stat.ML

Victor Boone This is my paper · ORCID

classification cs.LGstat.ML MSC 90C40

keywords MarkovdecisionprocessesaveragerewardregretminimizationasymptoticoptimalitycommunicatingMDPsexploration-co-exploration-exploitationregularization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims to settle, at first order, the regret problem for average-reward Markov decision processes under the communicating assumption: it exhibits an algorithm, ECoE*, whose expected regret after $T$ steps is $K(M)\log T + o(\log T)$ for every communicating model $M$ in a Bernoulli-reward, strongly product-form class, where $K(M)$ is the constant from the Boone–Maillard lower bound. Matching the lower bound requires the algorithm to learn $K(M)$ itself, even though $K(M)$ is discontinuous in the model; the paper handles this with a leveling transform and a regularized optimization that recovers the optimal exploration measure from noisy data. The algorithm balances exploration (playing suboptimal pairs for information), co-exploration (moving between components of near-optimal pairs), and exploitation (playing near-optimal pairs until regeneration), proving that each suboptimal pair is visited about $\mu^*(z)\log T$ times. The claimed consequence is that $K(M)$ is the exact first-order learning difficulty of a communicating MDP, up to $o(\log T)$.

What carries the argument

The load-bearing object is the regularized regret lower bound $\bar K_{\bar\epsilon}(M)$ and its unique optimizer $\mu^{\star}_{\bar\epsilon}$, built from three stabilizers: the leveling transform $[M]_\epsilon$, which raises rewards at near-optimal pairs so that threshold-optimal structure becomes exactly optimal; the set of $\epsilon$-uniform invariant measures, which keeps exploration fully supported and uniformly covers all pairs; and an $\epsilon_{\mathrm{conv}}$-strongly convex penalty, which selects a unique optimal exploration measure. Propositions 4, 5, and 6 show that as the regularizer shrinks, $\bar K_{\bar\epsilon}(M) \to K(M)$ and $\mu^{\star}_{\bar\epsilon} \to \mu^{\star}$, the central optimal exploration measure, while the map $M \mapsto (\bar K_{\bar\epsilon}(M), \mu^{\star}_{\bar\epsilon}(M))$ becomes continuous under the support-aware norm — this is what lets ECoE* compute near-optimal exploration policies from an empirical model $\hat M_t$. The algorithmic frame is the phase-based ECoE loop, using the square trick (ST) for co-exploration between components and a generalized log-likelihood ratio test to decide when information is lacking.

What would settle it

Evaluate the ratio of the uniformization to the convexification schedule given in (18): it is $\log(m)/\log\log(m)$, which diverges to infinity, whereas Assumption 6 (A5) requires it to tend to zero. This single arithmetic check shows the hypothesis of Proposition B.16 and Theorem C.1 is violated, so the central theorem as stated is not established by the paper's proof.

Watch

Extended reading notes

Core claim

The paper's central claim is that the asymptotic regret lower bound of Boone and Maillard (2025) is achievable: the ECoE* algorithm, with regularization schedule (18), satisfies $\mathrm{Reg}(T; M, \mathrm{ECoE}^*, s_0) \leq K(M)\log T + o(\log T)$ as $T \to \infty$ for every communicating MDP $M$ in a Bernoulli-reward ambient space with strong product structure (Assumptions 3 and 5). Here $K(M)$ is the lower-bound constant: the infimum, over invariant measures $\mu$, of the expected Bellman-gap cost under the constraint that enough information be gathered to reject every confusing model — a model that coincides with $M$ on optimal pairs but shares no gain-optimal policy. ECoE* estimates $K(M)$ from a maximum-likelihood model through a regularized surrogate that levels near-optimal pairs into optimal ones, uniformizes invariant measures, and convexifies the objective, and then uses the resulting exploration measure to schedule exploration, co-exploration among components of near-optimal pairs, and exploitation until regeneration. The proof shows each suboptimal pair is visited at the rate $\mu^*(z)\log T$ prescribed by the central optimal exploration measure, which makes the lower bound tight for the whole ambient class.

Load-bearing premise

The proof hinges on the two regularization schedules shrinking in a strict order: the uniformization schedule must tend to zero faster than the convexification schedule; with the paper's explicit choice (18) the order is reversed, so the proof does not cover the algorithm as stated.

Editorial extensions

If this is right

K(M) is confirmed as the first-order regret constant for communicating MDPs in the Bernoulli product-form class: every consistent algorithm pays at least $K(M)\log T$ in expectation, and ECoE* pays no more.
Suboptimal pairs are visited asymptotically at the rate $\mu^*(z)\log T$ dictated by the central optimal exploration measure, so the optimization problem (8) is not merely a bound but an explicit exploration prescription.
The discontinuity of $K(M)$ in the model does not prevent learning: the leveling-and-regularization mechanism produces an empirically computable estimator of $K(M)$ and of an optimal exploration policy that converges despite the discontinuity.
The regret guarantee holds uniformly over all communicating models in the ambient class, so the algorithm is universally asymptotically optimal rather than tuned to a single MDP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The regularization template — level near-optimal structure, uniformize the feasible set, convexify the objective — is likely transferable to other discontinuous problem-dependent constants in reinforcement learning, such as gap-dependent rates for weakly communicating MDPs, once matching lower bounds exist.
The square trick permits any exponent $\alpha \in (0,1)$ in $(\min_x N(x))^\alpha$, so the $o(\log T)$ cost of co-exploration travels can probably be tuned; a dedicated travel policy $\pi^\pm$ that moves between optimal components faster than the exploration policy $\pi^-$ would be a natural improvement of the constant hidden in the second-order term.
The Bernoulli and strong product-form restrictions are presented by the author as technical; extending the proof to single-parameter exponential families would broaden the result to a much larger class with the same skeleton.
A finite-horizon test on the two-loop models of Figures 1 and 2, where optimal pairs split across components and $K(M)$ has a closed form, would directly measure whether co-exploration travels remain sub-logarithmic as predicted.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Boone's paper is the right attempt at a real problem. It gives an algorithm family, ECoE*, explicitly built around the model-dependent constant K(M) from his lower bound with Maillard, and the machinery — co-exploration, the square trick, leveling, and regularized estimation of a discontinuous K — is genuinely new. If the main theorem goes through, it closes the communicating-MDP regret problem at first order. That is a big deal.

The paper as submitted does not prove the main theorem. Equation (18) sets epsilon_unif(m) = 1/log log m and epsilon_conv(m) = 1/log m, so epsilon_unif/epsilon_conv = log m / log log m, which diverges. Assumption 6(A5) requires epsilon_unif = o(epsilon_conv), and Proposition B.16 — the convergence of regularized exploration measures to the central measure mu*, used in Theorem C.1 — is stated only when that ratio goes to zero. The text says (18) satisfies Assumption 6; that is arithmetically false. Because Theorem C.1 and hence Theorem 7 are conditioned on Assumption 6, the claimed bound Reg(T) <= K(M) log T + o(log T) is not established for the algorithm as defined. This is the load-bearing flaw, and it is exactly what the stress-test identifies.

The flaw looks fixable: choose epsilon_conv to decay slower than epsilon_unif, for instance 1/sqrt(log log m), and re-check Assumption 6. But fixing it is not a formality — Proposition B.16, B.17, and parts of Appendix C rely on the relative rates, and the proof outline must be re-run with a corrected schedule.

Other soft spots are minor by comparison. The abstract overstates scope: Theorem 7 is for Bernoulli rewards and strong product-form ambient spaces, not literally all communicating MDPs. And ECoE* is oracle-based — computing K(M) and running the GLR tests are assumed free — so the result is about sample complexity, not computation. The author is upfront about this.

The appendix is serious and detailed, and the citation pattern to the prior lower bound is legitimate: this is a direct continuation, not self-citation padding. But the internal contradiction between (18) and Assumption 6 means the central claim is unproven on the paper's own terms.

Send it to peer review. A serious referee should require a corrected schedule and a clean verification of Assumption 6; this paper deserves that effort.

Referee Report

2 major / 4 minor

Summary. The paper proposes an algorithm, ECoE*, for average-reward communicating Markov decision processes and claims a regret upper bound of K(M) log T + o(log T), matching the lower bound of Boone and Maillard (2025). The algorithm is oracle-based and relies on a regularized estimate of the lower-bound constant K(M), with three regularization mechanisms: leveling near-optimal pairs, uniformization of invariant measures, and convexification. The central technical claim is Theorem 7, which follows from the general visit-count bound in Theorem C.1 under an explicit set of assumptions on the regularization schedule, Assumption 6. The proof structure is detailed: exploration, co-exploration, exploitation, and panic times are analyzed separately, and a large appendix develops continuity and convergence properties of the regularized lower bound.

Significance. If the main theorem is established, the paper solves a long-standing problem by giving the first matching upper bound for average-reward communicating MDPs, making the lower bound of Boone and Maillard tight. The leveling transform and the regularized lower bound are substantive technical contributions, and the paper is honest about the oracle-based nature of ECoE* and the computational difficulty of its subroutines. The proof is serious and largely self-contained, with explicit convergence statements (Propositions B.16, B.17, B.18) and a clear accounting of where each assumption is used. However, the paper is not yet in a publishable state because the stated regularization schedule violates a load-bearing assumption.

major comments (2)

[§5.2, Eq. (18); Appendix C.1, Assumption 6(A5); Appendix B.3.4, Proposition B.16] The regularization schedule in Eq. (18) does not satisfy Assumption 6(A5). The schedule sets epsilon_unif(m) = 1/log log m and epsilon_conv(m) = 1/log m, so epsilon_unif(m)/epsilon_conv(m) = log m / log log m, which diverges as m -> infinity. Assumption 6(A5) requires epsilon_unif(m) = o(epsilon_conv(m)). The statement in Appendix C.1 that "It is easy to check that Assumption 6 is satisfied for epsilon chosen as in (18)" is therefore arithmetically false. This is not a cosmetic issue: Proposition B.16, whose bound (B.25) is used in the proof of Lemma C.14 via Eq. (C.41)-(C.42), is stated under epsilon_unif/epsilon_conv + epsilon_conv + epsilon_lvl -> 0. Without this condition, the regularized exploration measures need not converge to the central optimal exploration measure mu*(M), so the constant multiplying log T in Theorem C.1 is not identified as K(M). Consequently, Theorem 7 is not proven for the algorithm with the hyperparameters stated in Eq. (18). The defect appears fixable by choosing epsilon_conv to decay strictly slower than epsilon_unif (for example, epsilon_conv(m) = 1/sqrt(log log m) with epsilon_unif(m) = 1/log log m), but the corrected schedule must be verified against all parts of Assumption 6, and the proof of Theorem C.1 must be re-run with that schedule.
[Appendix C.3.6, Eq. (C.44); Definition B.3] The exploration threshold m_{epsilon_0,T} in Eq. (C.44) divides by dmin(mu*), the definite minimum of the central optimal exploration measure. The paper does not establish that mu* is fully supported, and in general an optimal exploration measure for the optimization problem (8) may put zero mass on some pairs. If dmin(mu*) = 0, the threshold is undefined and the argument of Lemma C.17 and Lemma C.16 fails as written. The proof needs either an explicit argument that the central measure chosen in Definition B.3 has positive mass on every state-action pair under the ambient-space assumptions, or a modified threshold and lower-bound argument that avoids this division.

minor comments (4)

[Abstract] The phrase "a consequence challenge" should read "a consequential challenge".
[Introduction, Eq. (1)] The word "ominous algorithm" appears to be a typo for "omniscient algorithm".
[Section 5.4] The sentence "The proof of Theorem 1 is difficult" should refer to Theorem 7, not Theorem 1.
[Section 5.2 and Appendix C.1] Assumption 6 is introduced in Appendix C.1 but is referenced in Section 5.2 before it is stated; adding a forward reference or moving the assumption earlier would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bound is an independent constructive proof; the flagged violation of Assumption 6 by schedule (18) is a correctness gap, not a circular step.

full rationale

The paper's central claim is an upper bound matching the constant K(M) of Boone and Maillard (2025). That lower bound enters as a target value, not as a fitted parameter: ECoE* estimates K(M) from the empirical maximum-likelihood model through a regularized optimization problem, and Appendix C proves visit bounds of the form E[N_T(z)] <= mu*(z) log T / C(mu*,M) + o(log T) by separately controlling exploration, co-exploration, exploitation, and panic times. The final step, 'Because mu* is an optimizer of the optimization problem (8) associated to K(M), it immediately follows that ECoE* is asymptotically optimal,' is algebraic: it substitutes the already-proved visit bound into Reg = sum_z Delta*(z) E[N_T(z)] and uses the definition of K(M). No reduction of the theorem to its own input occurs. The reliance on the earlier lower bound is a genuine external theorem with stated assumptions, not an ansatz smuggled in by citation; the proof here does not assume the upper bound it claims. At the same time, the manuscript contains a serious correctness gap that is not circular: the schedule in (18) gives epsilon_unif(m)/epsilon_conv(m) = log(m)/log log(m) -> infinity, so Assumption 6(A5), which requires epsilon_unif(m) = o(epsilon_conv(m)), is false. The statement in Appendix C.1 that 'It is easy to check that Assumption 6 is satisfied for ¯epsilon chosen as in (18)' is arithmetically wrong, and Proposition B.16/Theorem C.1 therefore do not apply to the stated schedule as written. This is an invalid proof step, not a self-referential derivation, so it does not raise the circularity score.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

No data-fitted parameters beyond the MLE; the central load is carried by the prior lower bound K(M), the oracle assumption, and the regularization schedule. The leveling transform is a definition rather than an invented entity.

free parameters (1)

Regularization schedule (epsilon_lvl, epsilon_tst, epsilon_unif, epsilon_conv) = epsilon_lvl = epsilon_tst = 1/max(1, log log t); epsilon_unif = 1/max(1, log log m); epsilon_conv = 1/max(1, log m)
Hand-chosen vanishing schedules. They are not fitted to data, but the proof depends on their relative decay; as written they violate Assumption 6(A5).

assumptions (5)

domain assumption M is communicating with finite state-action space
Assumptions 1 and 2: the regret lower bound and algorithm analysis require finite pair space and finite diameter.
domain assumption Bernoulli rewards, product form, and strong product structure
Assumptions 3, 4, and 5: needed for continuity of the regularized lower bound and for the maximum likelihood estimator to be well-behaved.
ad hoc to paper Oracle for K, optimal exploration measures, and GLR tests
Section 5 assumes these subroutines are available 'by snapping fingers'; the paper states they are computationally difficult in general.
ad hoc to paper Regularization schedule satisfies Assumption 6, especially epsilon_unif = o(epsilon_conv)
Appendix C.1 lists conditions on the decay rates; Equation (18) violates the stated condition, making this premise load-bearing and currently unmet.
domain assumption Lower bound Reg(T; M, Lambda) >= K(M) log T + o(log T) from Boone and Maillard (2025)
The paper imports this prior theorem as the target constant; the upper bound result depends on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotically optimal regret in communicating Markov decision processes." pith.science (2026). https://pith.science/paper/3X2JTKJS

@misc{pith2026250518064,
  author       = {Pith},
  title        = {Pith review of: Asymptotically optimal regret in communicating Markov decision processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3X2JTKJS}},
  note         = {Machine review of arXiv:2505.18064}
}

abstract

In this paper, we present a learning algorithm that achieves asymptotically optimal regret for Markov decision processes in average reward under a communicating assumption. That is, given a communicating Markov decision process $M$, our algorithm has regret $K(M) \log(T) + \mathrm{o}(\log(T))$ where $T$ is the number of learning steps and $K(M)$ is the best possible constant. This algorithm works by explicitly tracking the constant $K(M)$ to learn optimally, then balances the trade-off between exploration (playing sub-optimally to gain information), co-exploration (playing optimally to gain information) and exploitation (playing optimally to score maximally). We further show that the function $K(M)$ is discontinuous, which is a consequence challenge for our approach. To that end, we describe a regularization mechanism to estimate $K(M)$ with arbitrary precision from empirical data.

Figures

Figures reproduced from arXiv: 2505.18064 by the authors.

**Figure 1.** A class of Markov decision processes with deterministic transitions parameterized by θ where co-exploration is troublesome. Arrows are choices of actions that deterministically lead to the pointed state and labels are rewards. Consider the class of Markov decision processes M := {Mθ : |θ| ≤ 1 2 } where Mθ is the model with Bernoulli rewards described [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** An example of discontinuity of the regret lower bound. The displayed transitions are deterministic and the labels represent the means of the attached Bernoulli rewards. Actions are distinguished by unique symbols for better readability of the contraction. Optimal pairs are colored in red. Bernoulli rewards, we can derive the regret lower bounds in closed form: K(M) = 4 10 kl(0.1, 0.5) and K(Mθ) ∼ θ→0+ θ kl(0.5 − θ, … view at source ↗

**Figure 3.** , the two optimal pairs correspond to the two loops 1 → 1 and 2 → 2 with associated gain g ∗ = 0.5. In the noisy copy M′ , only the left loop 1 → 1 is optimal with gain g ∗ = 0.52 After leveling M′ with threshold ϵ = 0.05, the right loop 2 → 2 becomes optimal again and the optimal gain is g ∗ = 0.52. So, M and [M]ϵ have the same optimal pairs and gain optimal policies. On this example, we observe that leveling with … view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: A discontinuity of ∆∗ (M). A class of Bernoulli reward models with deterministic transitions parameterized by θ ∈ Θ ≡ [− 1 2 , 1 2 ]. Arrows are choices of actions that deterministically lead to the pointed state and labels are mean rewards. This discontinuity is actua…

**Figure 5.** Figure 5: A discontinuity of Kϵ¯(M) when the product form (Assumption 4) is dropped. A set of Bernoulli reward models with deterministic transitions parameterized by θ ∈ Θ ≡ [0, 1]5 (to the left). Arrows are choices of actions that deterministically lead to the pointed state and…

**Figure 6.** Figure 6: Global overview of the different exploration periods as [PITH_FULL_IMAGE:figures/full_fig_p073_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 6 canonical work pages

[4]

_eprint: 2501.13013

URLhttps://arxiv.org/abs/2501.13013. _eprint: 2501.13013. Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research,...

arXiv
[9]

arXiv: 1205.4217

URL http://arxiv.org/abs/1205.4217. arXiv: 1205.4217. T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules.Advances in Applied Mathematics, 6(1):4–22, March

arXiv
[11]

Damianos Tranos and Alexandre Proutiere

arXiv: 1905.12425. Damianos Tranos and Alexandre Proutiere. Regret Analysis in Deterministic Reinforcement Learning. arXiv:2106.14338 [cs, stat], June

arXiv 1905
[13]

2 2.1.1 Randomized policies, their gain, bias & gap functions

112 Asymptotically optimal regret in communicating MDPs Index of notations 1(−) indicator function := defining equality,defined as ≡ syntactical equality,equal by definition = propositional equality,shown equal ∥−∥∗ support aware norm, Definition 9 a action A action space A(s) playable actions froms At random action at timet≥ 1 bπ(M) bias function ofπ, Se...

work page 2025
[1988]

Shipra Agrawal and Navin Goyal

doi: 10.1109/CDC.1988.194511. Shipra Agrawal and Navin Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem, April

work page arXiv 1988
[2006]

OptimisminReinforcementLearningand Kullback-Leibler Divergence.2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115–122, September

SarahFilippi, OlivierCappé, andAurélienGarivier. OptimisminReinforcementLearningand Kullback-Leibler Divergence.2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115–122, September

work page 2010
[2010]

Optimism in Reinforcement Learning and Kullback-Leibler Divergence

arXiv: 1004.5229. Ronan Fruit.Exploration-exploitation dilemma in Reinforcement Learning under various form of prior knowledge. PhD Thesis, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189,

work page Pith review arXiv
[2012]

arXiv:1111.1797 [cs]

URLhttp://arxiv.org/abs/1111.1797. arXiv:1111.1797 [cs]. Peter Auer and Ronald Ortner. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning. Proceedings of the 19th International Conference on Neural Information Processing Systems, December

arXiv

Show all 11 references

[2019]

Improved Analysis of UCRL2 with Empirical Bernstein Inequality.ArXiv, abs/2007.05456,

Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved Analysis of UCRL2 with Empirical Bernstein Inequality.ArXiv, abs/2007.05456,

2007 arXiv
[2021]

Zihan Zhang and Xiangyang Ji

arXiv: 2106.14338. Zihan Zhang and Xiangyang Ji. Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, editors,Advances in Neural Information Processing Sys...

arXiv
[2025]

_eprint: 2502.06480

URLhttps://arxiv.org/abs/2502.06480. _eprint: 2502.06480. Victor Boone and Odalric-Ambrym Maillard. The regret lower bound for communicating Markov Decision Processes,

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [4]

_eprint: 2501.13013

URLhttps://arxiv.org/abs/2501.13013. _eprint: 2501.13013. Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research,...

arXiv

[2] [9]

arXiv: 1205.4217

URL http://arxiv.org/abs/1205.4217. arXiv: 1205.4217. T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules.Advances in Applied Mathematics, 6(1):4–22, March

arXiv

[3] [11]

Damianos Tranos and Alexandre Proutiere

arXiv: 1905.12425. Damianos Tranos and Alexandre Proutiere. Regret Analysis in Deterministic Reinforcement Learning. arXiv:2106.14338 [cs, stat], June

arXiv 1905

[4] [13]

2 2.1.1 Randomized policies, their gain, bias & gap functions

112 Asymptotically optimal regret in communicating MDPs Index of notations 1(−) indicator function := defining equality,defined as ≡ syntactical equality,equal by definition = propositional equality,shown equal ∥−∥∗ support aware norm, Definition 9 a action A action space A(s) playable actions froms At random action at timet≥ 1 bπ(M) bias function ofπ, Se...

work page 2025

[5] [1988]

Shipra Agrawal and Navin Goyal

doi: 10.1109/CDC.1988.194511. Shipra Agrawal and Navin Goyal. Analysis of Thompson Sampling for the multi-armed bandit problem, April

work page arXiv 1988

[6] [2006]

OptimisminReinforcementLearningand Kullback-Leibler Divergence.2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115–122, September

SarahFilippi, OlivierCappé, andAurélienGarivier. OptimisminReinforcementLearningand Kullback-Leibler Divergence.2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115–122, September

work page 2010

[7] [2010]

Optimism in Reinforcement Learning and Kullback-Leibler Divergence

arXiv: 1004.5229. Ronan Fruit.Exploration-exploitation dilemma in Reinforcement Learning under various form of prior knowledge. PhD Thesis, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189,

work page Pith review arXiv

[8] [2012]

arXiv:1111.1797 [cs]

URLhttp://arxiv.org/abs/1111.1797. arXiv:1111.1797 [cs]. Peter Auer and Ronald Ortner. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning. Proceedings of the 19th International Conference on Neural Information Processing Systems, December

arXiv