On the Learning and Learnability of Quasimetrics

2022-06-30 · Tongzhou Wang, Phillip Isola

Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical). Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, little research has been done on the learning of quasimetrics. Our theoretical analysis reveals that a common class of learning algorithms, including unconstrained multilayer perceptrons (MLPs), provably fails to learn a quasimetric consistent with training data. In contrast, our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate its effectiveness over many common baselines.

📄 PDF Abstract BibTeX arXiv:2206.15478

Code (2)

ssnl/poisson_quasimetric_embedding 공식 구현 pytorch

quasimetric-learning/torch-quasimetric pytorch

Tasks

Q-LearningReinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Gravity Gravity is a kinematic approach to optimization based on gradients.

On the Learning of Quasimetrics

2021-09-29 · ICLR 2022 4 · Tongzhou Wang, Phillip Isola

Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making

2024-06-24 · Vivek Myers, Chongyi Zheng, Anca Dragan, Sergey Levine 외

Temporal distances lie at the heart of many algorithms for planning, control, and reinforcement learning that involve reaching goals, allowing one to estimate the transit time between two states. However, prior attempts …

Contrastive Learning Decision Making

Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning

2023-04-03 · Tongzhou Wang, Antonio Torralba, Phillip Isola, Amy Zhang

In goal-reaching reinforcement learning (RL), the optimal value function has a particular geometry, called quasimetric structure. This paper introduces Quasimetric Reinforcement Learning (QRL), a new RL method that utili…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Distribution Learnability and Robustness

2024-06-25 · NeurIPS 2023 11 · Shai Ben-David, Alex Bie, Gautam Kamath, Tosca Lechner

We examine the relationship between learnability and robust (or agnostic) learnability for the problem of distribution learning. We show that, contrary to other learning settings (e.g., PAC learning of function classes),…

PAC learning

Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings

2022-11-28 · Tongzhou Wang, Phillip Isola

Asymmetrical distance structures (quasimetrics) are ubiquitous in our lives and are gaining more attention in machine learning applications. Imposing such quasimetric structures in model representations has been shown to…

reinforcement-learning Reinforcement Learning (RL)