Learning the Minimal Representation of a Continuous State-Space Markov Decision Process from Transition Data

代表(政治) 状态空间 过渡(遗传学) 过程(计算) 马尔可夫决策过程 部分可观测马尔可夫决策过程 国家(计算机科学) 空格(标点符号) 计算机科学 马尔可夫链 马尔可夫过程 人工智能 数学 理论计算机科学 马尔可夫模型 数理经济学 机器学习 算法 统计 政治学 生物化学 化学 政治 法学 基因 操作系统
作者
Mohammed Amine Bennouna,Dessislava A. Pachamanova,Georgia Perakis,Omar Skali Lami
出处
期刊:Management Science [Institute for Operations Research and the Management Sciences]
标识
DOI:10.1287/mnsc.2022.01652
摘要

This paper proposes a framework for learning the most concise Markov decision process (MDP) model of a continuous state-space dynamic system from observed transition data. This setting is encountered in numerous important applications, such as patient treatment, online advertising, recommender systems, and estimation of treatment effects in econometrics. Most existing methods in offline reinforcement learning construct functional approximations of the value or the transition and reward functions, requiring complex and often not interpretable function approximators. Our approach instead relies on partitioning the system’s observation space into regions constituting states of a finite MDP representing the system. We discuss the theoretically minimal MDP representation that preserves the values and, therefore, the optimal policy of the dynamic system—in a sense, the optimal discretization. We formally define the problem of learning such a concise representation from transition data without exploration. Learning such a representation allows for enhanced tractability and, importantly, provides interpretability. To solve this problem, we introduce an in-sample property on partitions of the observation space we name coherence, and we show that if the class of possible partitions is of finite Vapnik-Chervonenkis dimension, any coherent partition with the transition data converges to the minimal representation of the system with provable finite-sample probably approximately correct convergence guarantees. This insight motivates our minimal representation learning algorithm that constructs from transition data an MDP representation that approximates the minimal representation of the system. We illustrate the effectiveness of the proposed framework through numerical experiments in both deterministic and stochastic environments as well as with real data. This paper was accepted by Chung Piaw Teo, optimization. Funding: The authors are very grateful to the Health Systems Initiative at MIT Sloan for financial support for this project. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2022.01652 .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
huang应助星星采纳,获得10
刚刚
刚刚
刚刚
Gj发布了新的文献求助10
1秒前
1秒前
1秒前
2秒前
爆米花应助儒雅盼芙采纳,获得10
2秒前
3秒前
星辰大海应助科研通管家采纳,获得10
3秒前
kaku完成签到,获得积分10
3秒前
英俊的铭应助科研通管家采纳,获得30
4秒前
浅海111完成签到,获得积分10
4秒前
4秒前
冷酷的妙之完成签到,获得积分10
4秒前
脑洞疼应助科研通管家采纳,获得10
4秒前
orixero应助科研通管家采纳,获得10
4秒前
JamesPei应助科研通管家采纳,获得10
4秒前
英姑应助科研通管家采纳,获得10
4秒前
5秒前
qfyyyyyyy应助科研通管家采纳,获得10
5秒前
李健应助科研通管家采纳,获得10
5秒前
慕青应助科研通管家采纳,获得10
5秒前
深情安青应助幺幺采纳,获得10
5秒前
李爱国应助科研通管家采纳,获得10
5秒前
青青完成签到,获得积分10
5秒前
大个应助科研通管家采纳,获得10
5秒前
香蕉觅云应助科研通管家采纳,获得10
5秒前
排骨炖豆角完成签到,获得积分10
6秒前
神探狄仁杰完成签到 ,获得积分10
6秒前
qfyyyyyyy应助科研通管家采纳,获得10
6秒前
天天快乐应助科研通管家采纳,获得10
6秒前
无极微光应助PXY采纳,获得20
6秒前
打打应助科研通管家采纳,获得10
6秒前
wanci应助科研通管家采纳,获得10
6秒前
6秒前
多喝水完成签到,获得积分10
6秒前
西瓜西瓜发布了新的文献求助10
7秒前
7秒前
爆米花应助大ma哈哈采纳,获得10
7秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
Autoparametric Resonance in Mechanical Systems 1000
Effects of Two Weeks of Red Light Therapy on Choroidal Thickness and Axial Length in Young Adults 700
Cosmos as Art Object: Studies in Plato's Timaeus and Other Dialogues 600
Management and the Arts 510
Matrix Methods in Data Mining and Pattern Recognition Second Edition 510
Common Foundations of American and East Asian Modernisation: From Alexander Hamilton to Junichero Koizumi 400
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 工程类 有机化学 化学工程 生物化学 计算机科学 内科学 物理 复合材料 催化作用 细胞生物学 无机化学 光电子学 物理化学 电极 基因
热门帖子
关注 科研通微信公众号,转发送积分 7670077
求助须知:如何正确求助?哪些是违规求助? 9237891
关于积分的说明 19890751
捐赠科研通 7239482
什么是DOI,文献DOI怎么找? 3284564
关于科研通互助平台的介绍 2443157
邀请新用户注册赠送积分活动 2286483