Pith. sign in

REVIEW 2 major objections 6 minor 47 references

Distances for Markov chains from sample streams

T0 review · 2 major / 6 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 introduces SOMCOT, a stochastic primal-dual method that estimates bisimulation/optimal-transport distances between finite Markov chains from sample transitions only, with finite-sample guarantees.

desk verdict Genuine advance in the LP reformulation, but the advertised sample-stream guarantee is not what Theorem 1 proves; the gap is admitted in Appendix B.4. read the letter →

arxiv 2505.18005 v1 pith:H5MDW7PV submitted 2025-05-23 cs.LG stat.ML

Sergio Calo , Anders Jonsson , Gergely Neu , Ludovic Schwartz , Javier Segovia-Aguas This is my paper
classification cs.LGstat.ML MSC 60J1090C0590C15
keywords bisimulationmetricsoptimaltransportMarkovchainssamplecomplexitystochasticprimal-dualoptimizationoccupancymeasureslinearprogrammingrepresentationlearning
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 tries to establish that the bisimulation metric, equivalently the optimal-transport distance, between two finite Markov chains can be estimated faithfully from sample transitions alone, without knowing either chain's transition probabilities. The authors derive a new linear-programming characterization of the distance whose constraints are written in terms of occupancy measures that can be sampled, and solve the resulting saddle-point problem with a stochastic primal-dual algorithm (SOMCOT). Theorem 1 guarantees that an epsilon-accurate estimate is produced with high probability after $\tilde{O}(|\mathcal{X}||\mathcal{Y}|(|\mathcal{X}|+|\mathcal{Y}|)/\epsilon^2)$ iterations, each using a single transition from each chain. If true, this is the first finite-sample guarantee for a problem that previously required full knowledge of dynamics, and it also yields encoder-decoder maps and differentiable distance estimates useful for representation learning.

What carries the argument

The load-bearing reformulation is a new linear program for the occupancy coupling $\mu$ whose constraints (6)-(8) involve only the marginal occupancy measures $\nu_{\mathcal{X}}$, $\nu_{\mathcal{Y}}$ and auxiliary conditional variables $\lambda_{\mathcal{X}}$, $\lambda_{\mathcal{Y}}$ instead of the transition kernels $P_{\mathcal{X}}$, $P_{\mathcal{Y}}$. This makes the Lagrangian's gradients expectations over $\nu_{\mathcal{X}}$ and $\nu_{\mathcal{Y}}$, so they can be estimated unbiasedly from sampled transitions; the algorithm then runs stochastic mirror descent on $(\mu, \lambda)$ and projected stochastic gradient ascent on dual variables $(\alpha, V)$, and outputs the time-averaged $\bar{\mu}_K$.

What would settle it

Compute the expected value of the indicator estimator $1\{X_k,X'_k=x,x'\}$ when $(X_k,X'_k)$ are consecutive pairs drawn from one long unreset trajectory rather than independent draws from $\nu_{\mathcal{X}}$; for a two-state chain with $\gamma>0$ this expectation differs from $\nu_{\mathcal{X}}(x,x')$ by a term decaying like $\gamma^t$, so running SOMCOT on identical chains with such stream data should reveal whether distance estimates fail to converge at the rate promised by Theorem 1.

Watch

Extended reading notes

Core claim

The paper claims that the bisimulation metric between two finite Markov chains, an optimal-transport distance over their infinite-horizon laws, can be estimated from sample transitions alone, with no knowledge of the transition kernels. Its Theorem 1 states that after $K$ iterations, each using one transition sampled from each chain's discounted occupancy measure, the averaged output satisfies $|\langle \bar{\mu}_K - \mu^*, c\rangle| = O\big(\tfrac{1}{\sqrt{K}(1-\gamma)}\big(\sqrt{|\mathcal{X}||\mathcal{Y}|(|\mathcal{X}|+|\mathcal{Y}|)} + \sqrt{(|\mathcal{X}|+|\mathcal{Y}|)\log(1/\delta)}\big)\big)$ with probability at least $1-\delta$, so $K = \tilde{O}(|\mathcal{X}||\mathcal{Y}|(|\mathcal{X}|+|\mathcal{Y}|)/((1-\gamma)^2\epsilon^2))$ iterations suffice for $\epsilon$-accuracy. This is the first finite-sample guarantee for computing such distances from data, in contrast to all earlier methods that require full transition dynamics.

Load-bearing premise

The guarantee assumes that each iteration receives independent draws from the discounted occupancy measures of the two chains, which in practice means restarting from the fixed initial state and simulating a geometric-horizon trajectory; a single unreset sample stream does not give unbiased gradient estimates, so the bounds in the paper no longer apply.

Editorial extensions

If this is right

  • For two finite Markov chains with $|\mathcal{X}|$ and $|\mathcal{Y}|$ states, an $\epsilon$-accurate distance estimate is guaranteed after $K = \tilde{O}(|\mathcal{X}||\mathcal{Y}|(|\mathcal{X}|+|\mathcal{Y}|)/((1-\gamma)^2\epsilon^2))$ iterations, each consuming a single transition from each chain.
  • The sample complexity scales as $|\mathcal{X}||\mathcal{Y}|(|\mathcal{X}|+|\mathcal{Y}|)$ rather than the ambient dimension $|\mathcal{X}|^2|\mathcal{Y}|^2$ of the optimization variable, and the scaling in $\epsilon$ is optimal up to logarithmic factors.
  • The side variables $\lambda_{\mathcal{X}}$ and $\lambda_{\mathcal{Y}}$ learn conditional distributions of the optimal coupling and act as encoder-decoder maps, so the same run produces a representation of the latent correspondence between the two chains.
  • The dual variables are derivatives of the distance with respect to the transition-occupancy distributions, which opens a path to differentiating the estimated distance for use as a loss function.
  • All previous computational approaches to bisimulation metrics require explicit transition kernels; this is the first method with guarantees from sample access alone.

Reading between the lines

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

  • If Theorem 1 transfers to the single sample stream setting that the authors only conjecture, then representation learning in reinforcement learning could use this distance as a theoretically grounded objective without a learned model; that transfer is not proven here.
  • The oracle assumption of independent discounted-occupancy draws is testable: a buffer of stored transitions with resampling may break correlations enough to make the unbiased estimators approximately valid, but how much correlation is tolerable remains an open quantitative question.
  • The same primal-dual machinery could be applied to other optimal-transport problems whose duals are expectations over stationary distributions, whenever unbiased occupancy samples are available.
  • The per-iteration computational cost $\Theta(|\mathcal{X}|^2|\mathcal{Y}|^2)$ may dominate in practice; sparse or factored updates exploiting the local structure of the gradient estimators would be a natural next step.
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.

Referee Report

2 major / 6 minor

Summary. The paper proposes SOMCOT, a stochastic primal-dual algorithm for estimating bisimulation metrics, equivalently optimal-transport distances, between finite Markov chains from sampled transitions rather than from explicit transition kernels. The authors introduce a new linear-programming characterization of occupancy couplings (Proposition 1), derive unbiased gradient estimators from draws of discounted occupancy measures, and prove a high-probability sample-complexity bound for the averaged primal output (Theorem 1). Experiments on block Markov chains and a discretized pendulum illustrate representation learning and model selection.

Significance. The theoretical core is valuable: the LP reformulation with auxiliary conditional variables is a genuine step beyond prior work, and the regret-based analysis with a rounding argument appears largely correct. If the result were stated for its actual sampling model, it would be the first finite-sample guarantee for estimating bisimulation/OT distances between Markov chains from data. However, the paper's advertised contribution is broader than its theorems: the title, abstract, and introduction promise estimation from arbitrary sample streams with one sample transition per iteration, whereas the proof requires i.i.d. draws from discounted occupancy measures, which need resetting and geometric-horizon rollouts. The paper itself concedes this gap in Appendix B.4. This mismatch is load-bearing and must be addressed before the claims match the analysis.

major comments (2)
  1. [Introduction; §3.2; Theorem 1; Appendix B.4] The central advertised claim is not supported by the analysis. The introduction states that the algorithm returns an ε-accurate estimate after O~(|X||Y|(|X|+|Y|)/ε^2) iterations with each iteration using a single sample transition from each chain, and the title promises 'sample streams'. Theorem 1, however, assumes that each iteration receives an i.i.d. pair (X_k,X'_k) ~ ν_X and (Y_k,Y'_k) ~ ν_Y from the discounted occupancy measures. As Appendix B.4 explains, drawing one such pair requires sampling a geometric stopping time G and simulating from the fixed initial state up to time G+1, costing Θ(1/(1−γ)) transitions per draw and requiring the ability to reset the chain. The total transition budget is therefore O((|X||Y|(|X|+|Y|)+(|X|+|Y|)log(1/δ))/((1−γ)^3 ε^2)) rather than the advertised one transition per iteration. The final paragraph of Appendix B.4 explicitly concedes that the unreset 'sample stream' setting is only expected to work, and Section 5 reports that all experiments use i.i.d. occupancy samples. The title, abstract, and introduction should be revised to describe the actual sampling model, or a mixing-time analysis for unreset streams should be supplied.
  2. [§3.2, Eqs. (11)–(14); Appendices C.3–C.4 and D] The unbiasedness that drives the proof fails for unreset streams. For the λ_X estimator, along a single unreset trajectory one has E[1{X_k=x, X'_k=x'} α_{X,k}(x,x',y) | F_{k-1}] = P[X_k=x] Σ_{x'} P_X(x'|x) α_{X,k}(x,x',y), whereas the true gradient in Eq. (28) is ν_X(x) Σ_{x'} P_X(x'|x) α_{X,k}(x,x',y). The ratio P[X_k=x]/ν_X(x) is time-dependent and is not controlled by any assumption in the paper. Since the martingale decomposition in Appendix D and the regret bounds in Lemmas 5–8 all rely on E[\tilde g_k | F_{k-1}] = ∇L, the analysis does not extend to the title's sample-stream setting. This is the key load-bearing gap between the public claim and the proven result.
minor comments (6)
  1. [Section 2] The symbol 'ν0,y' should be 'ν0,Y' for consistency with the notation ν0,X.
  2. [Section 3.2, Eq. (11)] The indicator '1{X_k,X'_k=x,x'}' should be written as '1{X_k=x, X'_k=x'}' for readability.
  3. [Appendix C.4] The proof text contains two typos: the second 'ηX = ...' should be 'ηY = ...', and 'the two probabilistic claims of Lemma 5 and 5' should refer to Lemmas 5 and 8.
  4. [Appendix D] The phrase 'with 1/eη = 0' is confusing; it should say that \tilde η is taken to infinity (equivalently, 1/\tilde η = 0).
  5. [Appendix F.1] The sentence 'we let X = Y = {1, 2, . . . , n} with n = 1' is incompatible with varying initial states in {2, . . . , n−1}; the intended value is likely n = 10 or similar.
  6. [Theorem 1] The learning rates stated in Theorem 1 differ from the optimized values used in the proof of Appendix C.4 by constant factors; the theorem should say the rates are valid up to numerical constants, or the proof should use the same values.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main result is an independent regret analysis; the sample-stream caveat is a scope mismatch, not circularity.

full rationale

The claimed derivation—Theorem 1's O( ... ) sample-complexity bound—is a genuine regret/duality-gap analysis of a stochastic primal-dual algorithm, not a restatement of its inputs. The unbiasedness of the gradient estimators in Eqs. (11)–(14) is checked directly against the Lagrangian gradients, and the bound follows from standard mirror-descent and martingale arguments in Appendices C–D. The LP equivalence in Proposition 1 is imported from the authors' prior Calo et al. (2024) characterization (Appendix A); this is a cited theorem with independent mathematical content whose assumptions do not include the present theorem, so its use is legitimate support rather than circularity. The only notable gap is scope, not circularity: the guarantee is for i.i.d. draws from occupancy measures ν_X and ν_Y, while the title promises 'sample streams.' Appendix B.4 itself concedes that generating such a draw costs a geometric-horizon trajectory and that using unreset streams is an unproven expectation—'we expect that, like most other RL algorithms, our method is also resilient to such abuse'—and Appendix F.2 confirms that 'all our experiments have made use of i.i.d. transitions sampled from the occupancy measures of the two chains.' This is a mismatch between the advertised and proven setting, and it should be weighed as a correctness/scope risk, but it is not a reduction of the result to its own inputs by construction. No fitted parameter is renamed as a prediction, no uniqueness theorem is invoked to forbid alternatives, and no equation is defined in terms of the quantity it purports to predict.

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

The central claim rests on (i) the inherited occupancy-coupling characterization of the authors' prior NeurIPS 2024 paper, (ii) an i.i.d. occupancy-sampling oracle that is stronger than the 'sample stream' of the title, and (iii) unproven bounds on the dual variables. The theory itself has no fitted parameters: the theorem sets the learning rates and the projection-box constants are fixed. The experiment-specific learning rates (Table 1) are hand-tuned but do not enter the theorem.

free parameters (4)
  • Initial primal learning rate eta_0 (experiments) = 40 (Figure 1), 20 (Figure 3), 0.1 (Figures 2a, 2b)
    Hand-tuned per experiment (Table 1); the paper reports convergence is very sensitive to this ('grueling' tuning, Appendix F.2). Does not enter the theorem, whose learning rates are set by K and state sizes.
  • Dual learning rate beta (experiments) = 0.2 (Figures 1, 2b), 0.5 (Figures 3, 2a)
    Hand-tuned per experiment (Table 1); ratio of eta to beta controls constraint-violation behavior (Appendix F.2). Does not enter the theorem.
  • Decay rate a for eta_k = eta_0 / sqrt(1 + a k) (experiments) = 0 (Figures 1, 3), 0.001 (Figure 2a), 0.05 (Figure 2b)
    Hand-tuned per experiment (Table 1) to balance early progress and late stability. Not part of the theoretical guarantee.
  • Minibatch size b (experiments) = 1 (Figures 1, 3), 8 (Figure 2a), 16 (Figure 2b)
    Hand-tuned per experiment (Table 1); the paper notes minibatching affects efficiency and stability but not the convergence properties (Appendix F.2).
assumptions (5)
  • domain assumption Calo et al. (2024) characterization: mu is an occupancy coupling of a bicausal coupling iff constraints (23)-(25) hold.
    Proposition 1 and its proof in Appendix A build on this published characterization (their Lemma 1); it is cited, not reproven.
  • domain assumption Optimal dual variables of the LP lie inside the boxes D_alpha = B_inf(0, 6/(1-gamma)) and D_V = B_inf(0, 2/(1-gamma)).
    Required for the saddle-point value with projected dual updates to equal d_gamma; stated without derivation in Section 3.2 and used in Lemmas 5 and 6.
  • domain assumption Sampling oracle: independent draws from the occupancy measures nu_X and nu_Y are available via reset plus geometric-horizon simulation.
    All gradient estimators (10)-(15) are unbiased only under this access model; Appendix B.4 describes the geometric-stopping procedure. No guarantee is given for a single unreset trajectory stream.
  • standard math Strong duality / Lagrange multiplier theorem for the LP (2) with constraints (6)-(8).
    Invoked in Section 3.2 to write d_gamma as the saddle point of the Lagrangian L.
  • standard math Perron-Frobenius uniqueness of the marginal occupancy measure (Lemma 12).
    Used in Appendix A to prove sum_y lambda_X(y|x) = 1 and in the rounding analysis of Appendix C.2.
invented entities (1)
  • lambda_X, lambda_Y auxiliary conditional distributions (LP lifting variables)
    purpose: Re-parametrize the occupancy-coupling constraints to remove explicit dependence on the transition kernels P_X and P_Y.
    Introduced in Proposition 1 (Eqs. 7-8). They are optimization variables, not empirical postulates; they carry no falsifiable handle outside this LP, but they are also not unsupported physical or mathematical objects in the 'graviton' sense, so this entry is benign.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distances for Markov chains from sample streams." pith.science (2026). https://pith.science/paper/H5MDW7PV

@misc{pith2026250518005,
  author       = {Pith},
  title        = {Pith review of: Distances for Markov chains from sample streams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H5MDW7PV}},
  note         = {Machine review of arXiv:2505.18005}
}
read the original abstract

Bisimulation metrics are powerful tools for measuring similarities between stochastic processes, and specifically Markov chains. Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees. However, these recent methods, as well as all previously known methods, assume full knowledge of the transition dynamics. This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available. In this work, we propose a stochastic optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models. Our approach is derived from a new linear programming (LP) formulation of bisimulation metrics, which we solve using a stochastic primal-dual optimization method. We provide theoretical guarantees on the sample complexity of the algorithm and validate its effectiveness through a series of empirical evaluations.

Figures

Figures reproduced from arXiv: 2505.18005 by the authors.

Figure 1
Figure 1. Encoder-decoder maps learned by the algorithm in a block Markov chain example ( [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Model selection results for random walks and the pendulum environment [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Distance matrices between instances after running [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The influence of the ratio between η and β on the convergence of SOMCOT for different chain sizes. Error and learning rates are shown on a logarithmic scale. To produce this plot, a decay rate of a = 0.001 was used for η. No decay was applied on β. and in particular th…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

47 extracted references · 38 canonical work pages

  1. [1]

    Near-linear time approximation algorithms for optimal transport via S inkhorn iteration

    Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via S inkhorn iteration. In Neural Information Processing Systems, 2017

    work page 2017

  2. [2]

    Wasserstein generative adversarial networks

    Martin Arjovsky, Soumith Chintala, and L \'e on Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning (ICML), pages 214--223, 2017

    work page 2017

  3. [3]

    Causal transport in discrete time and applications

    Julio Backhoff-Veraguas, Mathias Beiglbock, Yiqing Lin, and Anastasiia Zalashko. Causal transport in discrete time and applications. SIAM Journal on Optimization, 27 0 (4): 0 2528--2562, 2017

    work page 2017

  4. [4]

    Stochastic optimization for regularized wasserstein estimators

    Marin Ballu, Quentin Berthet, and Francis Bach. Stochastic optimization for regularized wasserstein estimators. In International Conference on Machine Learning, pages 602--612, 2020

    work page 2020

  5. [5]

    Distances for M arkov chains, and their differentiation

    Tristan Brug \`e re, Zhengchao Wan, and Yusu Wang. Distances for M arkov chains, and their differentiation. In International Conference on Algorithmic Learning Theory (ALT), pages 282--336, 2024

    work page 2024

  6. [6]

    Bisimulation metrics are optimal transport distances, and can be computed efficiently

    Sergio Calo, Anders Jonsson, Gergely Neu, Ludovic Schwartz, and Javier Segovia-Aguas . Bisimulation metrics are optimal transport distances, and can be computed efficiently. In Neural Information Processing Systems, 2024

    work page 2024

  7. [7]

    Scalable methods for computing state similarity in deterministic M arkov decision processes

    Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic M arkov decision processes. In AAAI Conference on Artificial Intelligence (AAAI), pages 10069--10076, 2020

    work page 2020

  8. [8]

    Prediction, Learning, and Games

    Nicol\`o Cesa-Bianchi and G\'abor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006

    2006

Show all 47 references
  1. [9]

    On the complexity of computing probabilistic bisimilarity

    Di Chen, Franck van Breugel, and James Worrell. On the complexity of computing probabilistic bisimilarity. In Foundations of Software Science and Computational Structures (FOSSACS), pages 437--451, 2012

    2012

  2. [10]

    Learning Representations via a Robust Behavioral Metric for Deep Reinforcement Learning

    Jianda Chen and Sinno Jialin Pan. Learning Representations via a Robust Behavioral Metric for Deep Reinforcement Learning . In Neural Information Processing Systems, 2022

    2022

  3. [11]

    Sinkhorn distances: Lightspeed computation of optimal transport

    Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Neural Information Processing Systems, 2013

    2013

  4. [12]

    Metrics for labeled Markov systems

    Jos \'e e Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labeled Markov systems. In International Conference on Concurrency Theory (CONCUR), pages 258--273, 1999

    1999

  5. [13]

    The metric analogue of weak bisimulation for probabilistic processes

    Jos\'ee Desharnais, Radha Jagadeesan, Vineet Gupta, and Prakash Panangaden. The metric analogue of weak bisimulation for probabilistic processes. In IEEE Symposium on Logic in Computer Science (LICS), pages 413--422, 2002

    2002

  6. [14]

    Provably Efficient RL with Rich Observations via Latent State Decoding

    Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably Efficient RL with Rich Observations via Latent State Decoding . In International Conference on Machine Learning (ICML), pages 1665--1674, 2019

    2019

  7. [15]

    Computational methods for adapted optimal transport

    Stephan Eckstein and Gudmund Pammer. Computational methods for adapted optimal transport. The Annals of Applied Probability, 34 0 (1A): 0 675--713, 2024

    2024

  8. [16]

    Learning with minibatch W asserstein: asymptotic and gradient properties

    Kilian Fatras, Younes Zine, R \'e mi Flamary, R \'e mi Gribonval, and Nicolas Courty. Learning with minibatch W asserstein: asymptotic and gradient properties. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2019

    2019

  9. [17]

    Minibatch optimal transport distances; analysis and applications

    Kilian Fatras, Younes Zine, Szymon Majewski, R \'e mi Flamary, R \'e mi Gribonval, and Nicolas Courty. Minibatch optimal transport distances; analysis and applications. arXiv preprint arXiv:2101.01792, 2021

    2021 arXiv

  10. [18]

    Metrics for finite Markov decision processes

    Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov decision processes. In Uncertainty in Artificial Intelligence (UAI), pages 162--169, 2004

    2004

  11. [19]

    Stochastic Optimization for Large-scale Optimal Transport

    Aude Genevay, Marco Cuturi, Gabriel Peyr\' e , and Francis Bach. Stochastic Optimization for Large-scale Optimal Transport . In Neural Information Processing Systems, 2016

    2016

  12. [20]

    Learning generative models with S inkhorn divergences

    Aude Genevay, Gabriel Peyr \'e , and Marco Cuturi. Learning generative models with S inkhorn divergences. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1608--1617, 2018

    2018

  13. [21]

    Equivalence notions and model minimization in Markov decision processes

    Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence, 147 0 (1-2): 0 163--223, 2003

    2003

  14. [22]

    A note on loss functions and error compounding in model-based reinforcement learning

    Nan Jiang. A note on loss functions and error compounding in model-based reinforcement learning. arXiv preprint arXiv:2404.09946, 2024

    2024 arXiv

  15. [23]

    Approximate policy iteration with bisimulation metrics

    Mete Kemertas and Allan Jepson. Approximate policy iteration with bisimulation metrics. Transactions on Machine Learning Research, 2022

    2022

  16. [24]

    Empirical regularized optimal transport: Statistical theory and applications

    Marcel Klatt, Carla Tameling, and Axel Munk. Empirical regularized optimal transport: Statistical theory and applications. SIAM Journal on Mathematics of Data Science, 2 0 (2): 0 419--443, 2020

    2020

  17. [25]

    Causal Transport Plans and Their Monge–Kantorovich Problems

    Rémi Lassalle. Causal Transport Plans and Their Monge–Kantorovich Problems . Taylor & Francis, 2018

    2018

  18. [26]

    Lillicrap, Jonathan J

    Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015

    2015 arXiv

  19. [27]

    Online sinkhorn: Optimal transport distances from sample streams

    Arthur Mensch and Gabriel Peyr \'e . Online sinkhorn: Optimal transport distances from sample streams. Advances in Neural Information Processing Systems, 33: 0 1657--1667, 2020

    2020

  20. [28]

    Communication and Concurrency

    Robin Milner. Communication and Concurrency. Prentice Hall, 1989

    1989

  21. [29]

    Bicausal optimal transport for M arkov chains via dynamic programming

    Vrettos Moulos. Bicausal optimal transport for M arkov chains via dynamic programming. In IEEE International Symposium on Information Theory (ISIT), pages 1688--1693, 2021

    2021

  22. [30]

    Nemirovski, A

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19: 0 1574--1609, 2009

    2009

  23. [31]

    Dealing with unbounded gradients in stochastic saddle-point optimization

    Gergely Neu and Nneka Okolo. Dealing with unbounded gradients in stochastic saddle-point optimization. In International Conference on Machine Learning (ICML), 2024

    2024

  24. [32]

    Optimal transport for stationary Markov chains via policy iteration

    Kevin O'Connor, Kevin McGoff, and Andrew B Nobel. Optimal transport for stationary Markov chains via policy iteration. Journal of Machine Learning Research, 23 0 (1): 0 2175--2226, 2022

    2022

  25. [33]

    A modern introduction to online learning

    Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019

    1912 arXiv

  26. [34]

    David M. R. Park. Concurrency and automata on infinite sequences. In GI Symposium on Theoretical Computer Science, volume 104 of Lecture Notes in Computer Science, pages 167--183. Springer, 1981

    1981

  27. [35]

    Computational optimal transport

    Gabriel Peyr \'e and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 11 0 (5-6): 0 355--607, 2019

    2019

  28. [36]

    Pflug and Alois Pichler

    Georg C. Pflug and Alois Pichler. A distance for multistage stochastic optimization models. SIAM Journal on Optimization, 22 0 (1): 0 1--23, 2012

    2012

  29. [37]

    Puterman

    Martin L. Puterman. M arkov Decision Processes: Discrete Stochastic Dynamic Programming . Wiley-Interscience, April 1994

    1994

  30. [38]

    On equivalence of martingale tail bounds and deterministic regret inequalities

    Alexander Rakhlin and Karthik Sridharan. On equivalence of martingale tail bounds and deterministic regret inequalities. In Conference on Learning Theory, pages 1704--1722. PMLR, 2017

    2017

  31. [39]

    Mastering atari, go, chess and shogi by planning with a learned model

    Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588 0 (7839): 0 604--609, 2020

    2020

  32. [40]

    Large-scale optimal transport and mapping estimation

    Vivien Seguy, Bharath Bhushan Damodaran, R \'e mi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. In International Conference on Learning Representations (ICLR), 2018

    2018

  33. [41]

    High rank path development: an approach to learning the filtration of stochastic processes

    Jiajie Tao, Hao Ni, and Chong Liu. High rank path development: an approach to learning the filtration of stochastic processes. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  34. [42]

    Optimal Transport for structured data with application on graphs

    Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary. Optimal Transport for structured data with application on graphs . In International Conference on Machine Learning (ICML), pages 6275--6284, 2019

    2019

  35. [43]

    Gymnasium: A standard interface for reinforcement learning environments

    Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goul \ a o, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024

    2024 arXiv

  36. [44]

    An algorithm for quantitative verification of probabilistic transition systems

    Franck van Breugel and James Worrell. An algorithm for quantitative verification of probabilistic transition systems. In International Conference on Concurrency Theory (CONCUR), pages 336--350, 2001

    2001

  37. [45]

    Optimal transport: old and new, volume 338

    C \'e dric Villani. Optimal transport: old and new, volume 338. Springer, 2009

    2009

  38. [46]

    COT-GAN : Generating sequential data via causal optimal transport

    Tianlin Xu, Li Kevin Wenliang, Michael Munn, and Beatrice Acciaio. COT-GAN : Generating sequential data via causal optimal transport. Advances in neural information processing systems, 33: 0 8798--8809, 2020

    2020

  39. [47]

    Learning Invariant Representations for Reinforcement Learning without Reconstruction

    Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning Invariant Representations for Reinforcement Learning without Reconstruction . In International Conference on Learning Representations (ICLR), 2021

    2021

Pith tools

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