Scalable methods for computing state similarity in deterministic Markov Decision Processes
We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs). Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour. Unfortunately, their computation is expensive and requires a tabular representation of the states, which has thus far rendered them impractical for large problems. In this paper we present a new version of the metric that is tied to a behavior policy in an MDP, along with an analysis of its theoretical properties. We then present two new algorithms for approximating bisimulation metrics in large, deterministic MDPs. The first does so via sampling and is guaranteed to converge to the true metric. The second is a differentiable loss which allows us to learn an approximation even for continuous state MDPs, which prior to this work had not been possible.
Code (1)
Similar Papers 제목 키워드 기반
N2N: A Parallel Framework for Large-Scale MILP under Distributed Memory
Parallelization has emerged as a promising approach for accelerating MILP solving. However, the complexity of the branch-and-bound (B&B) framework and the numerous effective algorithm components in MILP solvers make it d…
Deterministic Reservoir Computing for Chaotic Time Series Prediction
Reservoir Computing was shown in recent years to be useful as efficient to learn networks in the field of time series tasks. Their randomized initialization, a computational benefit, results in drawbacks in theoretical a…
PredictionTime SeriesTime Series ForecastingTime Series PredictionScalable Spectral Clustering Using Random Binning Features
Spectral clustering is one of the most effective clustering approaches that capture hidden cluster structures in the data. However, it does not scale well to large-scale problems due to its quadratic complexity in constr…
Clusteringgraph constructionGraph SimilarityImage/Document ClusteringPoint-Set Kernel Clustering
Measuring similarity between two objects is the core operation in existing clustering algorithms in grouping similar objects into clusters. This paper introduces a new similarity measure called point-set kernel which com…
ClusteringSemantic SegmentationAccurate 3D Finger Knuckle Recognition Using Auto-Generated Similarity Functions
Contactless 3D finger knuckle is an emerging biometric identifier, which can provide a promising alternative for personal identification. To maximize its potential, feature representation and matching are the two critica…
3D geometry