Model-Based Exploration in Monitored Markov Decision Processes Article Swipe

PDF

Alireza Kazemipour , Simone Parisi , Matthew E. Taylor , Michael Bowling ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2502.16772

A tenet of reinforcement learning is that the agent always observes rewards. However, this is not true in many realistic settings, e.g., a human observer may not always be available to provide rewards, sensors may be limited or malfunctioning, or rewards may be inaccessible during deployment. Monitored Markov decision processes (Mon-MDPs) have recently been proposed to model such settings. However, existing Mon-MDP algorithms have several limitations: they do not fully exploit the problem structure, cannot leverage a known monitor, lack worst-case guarantees for 'unsolvable' Mon-MDPs without specific initialization, and offer only asymptotic convergence proofs. This paper makes three contributions. First, we introduce a model-based algorithm for Mon-MDPs that addresses these shortcomings. The algorithm employs two instances of model-based interval estimation: one to ensure that observable rewards are reliably captured, and another to learn the minimax-optimal policy. Second, we empirically demonstrate the advantages. We show faster convergence than prior algorithms in over four dozen benchmarks, and even more dramatic improvement when the monitoring process is known. Third, we present the first finite-sample bound on performance. We show convergence to a minimax-optimal policy even when some rewards are never observable.

Related Topics

Exploration Of North America

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2502.16772
PDF: https://arxiv.org/pdf/2502.16772
OA Status: green
OpenAlex ID: https://openalex.org/W4417094986

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4417094986

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2502.16772

Digital Object Identifier
Title: Model-Based Exploration in Monitored Markov Decision Processes

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-02-24

Full publication date if available
Authors: Alireza Kazemipour, Simone Parisi, Matthew E. Taylor, Michael Bowling

List of authors in order
Landing page: https://arxiv.org/abs/2502.16772

Publisher landing page
PDF URL: https://arxiv.org/pdf/2502.16772

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2502.16772

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4417094986
doi	https://doi.org/10.48550/arxiv.2502.16772
ids.doi	https://doi.org/10.48550/arxiv.2502.16772
ids.openalex	https://openalex.org/W4417094986
fwci
type	preprint
title	Model-Based Exploration in Monitored Markov Decision Processes
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2502.16772
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2502.16772
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2502.16772
locations[1].id	doi:10.48550/arxiv.2502.16772
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2502.16772
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5054536993
authorships[0].author.orcid	https://orcid.org/0000-0001-7658-6288
authorships[0].author.display_name	Alireza Kazemipour
authorships[0].author_position	first
authorships[0].raw_author_name	Kazemipour, Alireza
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5055633714
authorships[1].author.orcid	https://orcid.org/0000-0003-3886-8131
authorships[1].author.display_name	Simone Parisi
authorships[1].author_position	middle
authorships[1].raw_author_name	Parisi, Simone
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5070914351
authorships[2].author.orcid	https://orcid.org/0000-0001-8946-0211
authorships[2].author.display_name	Matthew E. Taylor
authorships[2].author_position	middle
authorships[2].raw_author_name	Taylor, Matthew E.
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5081163135
authorships[3].author.orcid	https://orcid.org/0000-0003-2960-8418
authorships[3].author.display_name	Michael Bowling
authorships[3].author_position	last
authorships[3].raw_author_name	Bowling, Michael
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2502.16772
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Model-Based Exploration in Monitored Markov Decision Processes
has_fulltext	False
is_retracted	False
updated_date	2025-12-07T17:40:25.070200
primary_topic
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2502.16772
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2502.16772
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2502.16772
primary_location.id	pmh:oai:arXiv.org:2502.16772
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2502.16772
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2502.16772
publication_date	2025-02-24
publication_year	2025
referenced_works_count	0
abstract_inverted_index.A	0
abstract_inverted_index.a	22, 76, 102, 178
abstract_inverted_index.We	142, 174
abstract_inverted_index.be	28, 35, 42
abstract_inverted_index.do	67
abstract_inverted_index.in	17, 149
abstract_inverted_index.is	5, 14, 163
abstract_inverted_index.of	2, 116
abstract_inverted_index.on	172
abstract_inverted_index.or	37, 39
abstract_inverted_index.to	30, 55, 121, 131, 177
abstract_inverted_index.we	100, 137, 166
abstract_inverted_index.The	111
abstract_inverted_index.and	88, 129, 154
abstract_inverted_index.are	126, 185
abstract_inverted_index.for	82, 105
abstract_inverted_index.may	25, 34, 41
abstract_inverted_index.not	15, 26, 68
abstract_inverted_index.one	120
abstract_inverted_index.the	7, 71, 133, 140, 160, 168
abstract_inverted_index.two	114
abstract_inverted_index.This	94
abstract_inverted_index.been	53
abstract_inverted_index.even	155, 181
abstract_inverted_index.four	151
abstract_inverted_index.have	51, 63
abstract_inverted_index.lack	79
abstract_inverted_index.many	18
abstract_inverted_index.more	156
abstract_inverted_index.only	90
abstract_inverted_index.over	150
abstract_inverted_index.show	143, 175
abstract_inverted_index.some	183
abstract_inverted_index.such	57
abstract_inverted_index.than	146
abstract_inverted_index.that	6, 107, 123
abstract_inverted_index.they	66
abstract_inverted_index.this	13
abstract_inverted_index.true	16
abstract_inverted_index.when	159, 182
abstract_inverted_index.agent	8
abstract_inverted_index.bound	171
abstract_inverted_index.dozen	152
abstract_inverted_index.e.g.,	21
abstract_inverted_index.first	169
abstract_inverted_index.fully	69
abstract_inverted_index.human	23
abstract_inverted_index.known	77
abstract_inverted_index.learn	132
abstract_inverted_index.makes	96
abstract_inverted_index.model	56
abstract_inverted_index.never	186
abstract_inverted_index.offer	89
abstract_inverted_index.paper	95
abstract_inverted_index.prior	147
abstract_inverted_index.tenet	1
abstract_inverted_index.these	109
abstract_inverted_index.three	97
abstract_inverted_index.First,	99
abstract_inverted_index.Markov	47
abstract_inverted_index.Third,	165
abstract_inverted_index.always	9, 27
abstract_inverted_index.cannot	74
abstract_inverted_index.during	44
abstract_inverted_index.ensure	122
abstract_inverted_index.faster	144
abstract_inverted_index.known.	164
abstract_inverted_index.policy	180
abstract_inverted_index.Mon-MDP	61
abstract_inverted_index.Second,	136
abstract_inverted_index.another	130
abstract_inverted_index.employs	113
abstract_inverted_index.exploit	70
abstract_inverted_index.limited	36
abstract_inverted_index.policy.	135
abstract_inverted_index.present	167
abstract_inverted_index.problem	72
abstract_inverted_index.process	162
abstract_inverted_index.proofs.	93
abstract_inverted_index.provide	31
abstract_inverted_index.rewards	40, 125, 184
abstract_inverted_index.sensors	33
abstract_inverted_index.several	64
abstract_inverted_index.without	85
abstract_inverted_index.However,	12, 59
abstract_inverted_index.Mon-MDPs	84, 106
abstract_inverted_index.decision	48
abstract_inverted_index.dramatic	157
abstract_inverted_index.existing	60
abstract_inverted_index.interval	118
abstract_inverted_index.learning	4
abstract_inverted_index.leverage	75
abstract_inverted_index.monitor,	78
abstract_inverted_index.observer	24
abstract_inverted_index.observes	10
abstract_inverted_index.proposed	54
abstract_inverted_index.recently	52
abstract_inverted_index.reliably	127
abstract_inverted_index.rewards,	32
abstract_inverted_index.rewards.	11
abstract_inverted_index.specific	86
abstract_inverted_index.Monitored	46
abstract_inverted_index.addresses	108
abstract_inverted_index.algorithm	104, 112
abstract_inverted_index.available	29
abstract_inverted_index.captured,	128
abstract_inverted_index.instances	115
abstract_inverted_index.introduce	101
abstract_inverted_index.processes	49
abstract_inverted_index.realistic	19
abstract_inverted_index.settings,	20
abstract_inverted_index.settings.	58
abstract_inverted_index.(Mon-MDPs)	50
abstract_inverted_index.algorithms	62, 148
abstract_inverted_index.asymptotic	91
abstract_inverted_index.guarantees	81
abstract_inverted_index.monitoring	161
abstract_inverted_index.observable	124
abstract_inverted_index.structure,	73
abstract_inverted_index.worst-case	80
abstract_inverted_index.advantages.	141
abstract_inverted_index.benchmarks,	153
abstract_inverted_index.convergence	92, 145, 176
abstract_inverted_index.demonstrate	139
abstract_inverted_index.deployment.	45
abstract_inverted_index.empirically	138
abstract_inverted_index.estimation:	119
abstract_inverted_index.improvement	158
abstract_inverted_index.model-based	103, 117
abstract_inverted_index.observable.	187
abstract_inverted_index.'unsolvable'	83
abstract_inverted_index.inaccessible	43
abstract_inverted_index.limitations:	65
abstract_inverted_index.performance.	173
abstract_inverted_index.finite-sample	170
abstract_inverted_index.reinforcement	3
abstract_inverted_index.shortcomings.	110
abstract_inverted_index.contributions.	98
abstract_inverted_index.initialization,	87
abstract_inverted_index.malfunctioning,	38
abstract_inverted_index.minimax-optimal	134, 179
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile