Risk Estimation in a Markov Cost Process: Lower and Upper Bounds Article Swipe
Sanjay P. Bhat
,
L. A. Prashanth
,
Gugan Thoppe
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2310.11389
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2310.11389
We tackle the problem of estimating risk measures of the infinite-horizon discounted cost within a Markov cost process. The risk measures we study include variance, Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR). First, we show that estimating any of these risk measures with $ε$-accuracy, either in expected or high-probability sense, requires at least $Ω(1/ε^2)$ samples. Then, using a truncation scheme, we derive an upper bound for the CVaR and variance estimation. This bound matches our lower bound up to logarithmic factors. Finally, we discuss an extension of our estimation scheme that covers more general risk measures satisfying a certain continuity criterion, e.g., spectral risk measures, utility-based shortfall risk. To the best of our knowledge, our work is the first to provide lower and upper bounds for estimating any risk measure beyond the mean within a Markovian setting. Our lower bounds also extend to the infinite-horizon discounted costs' mean. Even in that case, our lower bound of $Ω(1/ε^2) $ improves upon the existing $Ω(1/ε)$ bound [13].
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2310.11389
- https://arxiv.org/pdf/2310.11389
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4387800241
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4387800241Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2310.11389Digital Object Identifier
- Title
-
Risk Estimation in a Markov Cost Process: Lower and Upper BoundsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-10-17Full publication date if available
- Authors
-
Sanjay P. Bhat, L. A. Prashanth, Gugan ThoppeList of authors in order
- Landing page
-
https://arxiv.org/abs/2310.11389Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2310.11389Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2310.11389Direct OA link when available
- Concepts
-
CVAR, Upper and lower bounds, Mathematics, Expected shortfall, Risk measure, Logarithm, Mathematical optimization, Markov process, Statistics, Applied mathematics, Econometrics, Economics, Risk management, Finance, Mathematical analysis, PortfolioTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4387800241 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2310.11389 |
| ids.doi | https://doi.org/10.48550/arxiv.2310.11389 |
| ids.openalex | https://openalex.org/W4387800241 |
| fwci | |
| type | preprint |
| title | Risk Estimation in a Markov Cost Process: Lower and Upper Bounds |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10136 |
| topics[0].field.id | https://openalex.org/fields/26 |
| topics[0].field.display_name | Mathematics |
| topics[0].score | 0.9868999719619751 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2613 |
| topics[0].subfield.display_name | Statistics and Probability |
| topics[0].display_name | Statistical Methods and Inference |
| topics[1].id | https://openalex.org/T11413 |
| topics[1].field.id | https://openalex.org/fields/18 |
| topics[1].field.display_name | Decision Sciences |
| topics[1].score | 0.9793999791145325 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1803 |
| topics[1].subfield.display_name | Management Science and Operations Research |
| topics[1].display_name | Risk and Portfolio Optimization |
| topics[2].id | https://openalex.org/T10804 |
| topics[2].field.id | https://openalex.org/fields/20 |
| topics[2].field.display_name | Economics, Econometrics and Finance |
| topics[2].score | 0.9706000089645386 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2002 |
| topics[2].subfield.display_name | Economics and Econometrics |
| topics[2].display_name | Health Systems, Economic Evaluations, Quality of Life |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2779922397 |
| concepts[0].level | 4 |
| concepts[0].score | 0.9713413715362549 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q5014755 |
| concepts[0].display_name | CVAR |
| concepts[1].id | https://openalex.org/C77553402 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7897345423698425 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[1].display_name | Upper and lower bounds |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.6889854669570923 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C5496284 |
| concepts[3].level | 3 |
| concepts[3].score | 0.4988057613372803 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q5420856 |
| concepts[3].display_name | Expected shortfall |
| concepts[4].id | https://openalex.org/C2781472820 |
| concepts[4].level | 3 |
| concepts[4].score | 0.48200860619544983 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2154759 |
| concepts[4].display_name | Risk measure |
| concepts[5].id | https://openalex.org/C39927690 |
| concepts[5].level | 2 |
| concepts[5].score | 0.46752500534057617 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q11197 |
| concepts[5].display_name | Logarithm |
| concepts[6].id | https://openalex.org/C126255220 |
| concepts[6].level | 1 |
| concepts[6].score | 0.46514973044395447 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[6].display_name | Mathematical optimization |
| concepts[7].id | https://openalex.org/C159886148 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4505123496055603 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q176645 |
| concepts[7].display_name | Markov process |
| concepts[8].id | https://openalex.org/C105795698 |
| concepts[8].level | 1 |
| concepts[8].score | 0.42395448684692383 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[8].display_name | Statistics |
| concepts[9].id | https://openalex.org/C28826006 |
| concepts[9].level | 1 |
| concepts[9].score | 0.38014844059944153 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q33521 |
| concepts[9].display_name | Applied mathematics |
| concepts[10].id | https://openalex.org/C149782125 |
| concepts[10].level | 1 |
| concepts[10].score | 0.3401023745536804 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q160039 |
| concepts[10].display_name | Econometrics |
| concepts[11].id | https://openalex.org/C162324750 |
| concepts[11].level | 0 |
| concepts[11].score | 0.20730340480804443 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q8134 |
| concepts[11].display_name | Economics |
| concepts[12].id | https://openalex.org/C32896092 |
| concepts[12].level | 2 |
| concepts[12].score | 0.1310587227344513 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q189447 |
| concepts[12].display_name | Risk management |
| concepts[13].id | https://openalex.org/C10138342 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0910772979259491 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q43015 |
| concepts[13].display_name | Finance |
| concepts[14].id | https://openalex.org/C134306372 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[14].display_name | Mathematical analysis |
| concepts[15].id | https://openalex.org/C2780821815 |
| concepts[15].level | 2 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q5340806 |
| concepts[15].display_name | Portfolio |
| keywords[0].id | https://openalex.org/keywords/cvar |
| keywords[0].score | 0.9713413715362549 |
| keywords[0].display_name | CVAR |
| keywords[1].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[1].score | 0.7897345423698425 |
| keywords[1].display_name | Upper and lower bounds |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.6889854669570923 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/expected-shortfall |
| keywords[3].score | 0.4988057613372803 |
| keywords[3].display_name | Expected shortfall |
| keywords[4].id | https://openalex.org/keywords/risk-measure |
| keywords[4].score | 0.48200860619544983 |
| keywords[4].display_name | Risk measure |
| keywords[5].id | https://openalex.org/keywords/logarithm |
| keywords[5].score | 0.46752500534057617 |
| keywords[5].display_name | Logarithm |
| keywords[6].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[6].score | 0.46514973044395447 |
| keywords[6].display_name | Mathematical optimization |
| keywords[7].id | https://openalex.org/keywords/markov-process |
| keywords[7].score | 0.4505123496055603 |
| keywords[7].display_name | Markov process |
| keywords[8].id | https://openalex.org/keywords/statistics |
| keywords[8].score | 0.42395448684692383 |
| keywords[8].display_name | Statistics |
| keywords[9].id | https://openalex.org/keywords/applied-mathematics |
| keywords[9].score | 0.38014844059944153 |
| keywords[9].display_name | Applied mathematics |
| keywords[10].id | https://openalex.org/keywords/econometrics |
| keywords[10].score | 0.3401023745536804 |
| keywords[10].display_name | Econometrics |
| keywords[11].id | https://openalex.org/keywords/economics |
| keywords[11].score | 0.20730340480804443 |
| keywords[11].display_name | Economics |
| keywords[12].id | https://openalex.org/keywords/risk-management |
| keywords[12].score | 0.1310587227344513 |
| keywords[12].display_name | Risk management |
| keywords[13].id | https://openalex.org/keywords/finance |
| keywords[13].score | 0.0910772979259491 |
| keywords[13].display_name | Finance |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2310.11389 |
| 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/2310.11389 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| 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/2310.11389 |
| locations[1].id | doi:10.48550/arxiv.2310.11389 |
| 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 | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| 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.2310.11389 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5039306255 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-8595-6081 |
| authorships[0].author.display_name | Sanjay P. Bhat |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bhat, Sanjay |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5068379567 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | L. A. Prashanth |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | A., Prashanth L. |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5047138399 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5066-6589 |
| authorships[2].author.display_name | Gugan Thoppe |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Thoppe, Gugan |
| authorships[2].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/2310.11389 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-10-21T00:00:00 |
| display_name | Risk Estimation in a Markov Cost Process: Lower and Upper Bounds |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10136 |
| primary_topic.field.id | https://openalex.org/fields/26 |
| primary_topic.field.display_name | Mathematics |
| primary_topic.score | 0.9868999719619751 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2613 |
| primary_topic.subfield.display_name | Statistics and Probability |
| primary_topic.display_name | Statistical Methods and Inference |
| related_works | https://openalex.org/W2232143283, https://openalex.org/W1647779468, https://openalex.org/W2499931925, https://openalex.org/W2002736235, https://openalex.org/W1997933673, https://openalex.org/W2384833971, https://openalex.org/W48101171, https://openalex.org/W3163306334, https://openalex.org/W2031780815, https://openalex.org/W2770173738 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2310.11389 |
| 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/2310.11389 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| 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/2310.11389 |
| primary_location.id | pmh:oai:arXiv.org:2310.11389 |
| 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/2310.11389 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| 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/2310.11389 |
| publication_date | 2023-10-17 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.$ | 156 |
| abstract_inverted_index.a | 14, 56, 96, 133 |
| abstract_inverted_index.To | 107 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.an | 61, 83 |
| abstract_inverted_index.at | 50 |
| abstract_inverted_index.in | 44, 148 |
| abstract_inverted_index.is | 115 |
| abstract_inverted_index.of | 4, 8, 37, 85, 110, 154 |
| abstract_inverted_index.or | 46 |
| abstract_inverted_index.to | 77, 118, 141 |
| abstract_inverted_index.up | 76 |
| abstract_inverted_index.we | 21, 32, 59, 81 |
| abstract_inverted_index.Our | 136 |
| abstract_inverted_index.The | 18 |
| abstract_inverted_index.and | 27, 67, 121 |
| abstract_inverted_index.any | 36, 126 |
| abstract_inverted_index.for | 64, 124 |
| abstract_inverted_index.our | 73, 86, 111, 113, 151 |
| abstract_inverted_index.the | 2, 9, 65, 108, 116, 130, 142, 159 |
| abstract_inverted_index.CVaR | 66 |
| abstract_inverted_index.Even | 147 |
| abstract_inverted_index.This | 70 |
| abstract_inverted_index.also | 139 |
| abstract_inverted_index.best | 109 |
| abstract_inverted_index.cost | 12, 16 |
| abstract_inverted_index.mean | 131 |
| abstract_inverted_index.more | 91 |
| abstract_inverted_index.risk | 6, 19, 39, 93, 102, 127 |
| abstract_inverted_index.show | 33 |
| abstract_inverted_index.that | 34, 89, 149 |
| abstract_inverted_index.upon | 158 |
| abstract_inverted_index.with | 41 |
| abstract_inverted_index.work | 114 |
| abstract_inverted_index.Then, | 54 |
| abstract_inverted_index.[13]. | 163 |
| abstract_inverted_index.bound | 63, 71, 75, 153, 162 |
| abstract_inverted_index.case, | 150 |
| abstract_inverted_index.e.g., | 100 |
| abstract_inverted_index.first | 117 |
| abstract_inverted_index.least | 51 |
| abstract_inverted_index.lower | 74, 120, 137, 152 |
| abstract_inverted_index.mean. | 146 |
| abstract_inverted_index.risk. | 106 |
| abstract_inverted_index.study | 22 |
| abstract_inverted_index.these | 38 |
| abstract_inverted_index.upper | 62, 122 |
| abstract_inverted_index.using | 55 |
| abstract_inverted_index.(VaR), | 26 |
| abstract_inverted_index.First, | 31 |
| abstract_inverted_index.Markov | 15 |
| abstract_inverted_index.beyond | 129 |
| abstract_inverted_index.bounds | 123, 138 |
| abstract_inverted_index.costs' | 145 |
| abstract_inverted_index.covers | 90 |
| abstract_inverted_index.derive | 60 |
| abstract_inverted_index.either | 43 |
| abstract_inverted_index.extend | 140 |
| abstract_inverted_index.scheme | 88 |
| abstract_inverted_index.sense, | 48 |
| abstract_inverted_index.tackle | 1 |
| abstract_inverted_index.within | 13, 132 |
| abstract_inverted_index.(CVaR). | 30 |
| abstract_inverted_index.certain | 97 |
| abstract_inverted_index.discuss | 82 |
| abstract_inverted_index.general | 92 |
| abstract_inverted_index.include | 23 |
| abstract_inverted_index.matches | 72 |
| abstract_inverted_index.measure | 128 |
| abstract_inverted_index.problem | 3 |
| abstract_inverted_index.provide | 119 |
| abstract_inverted_index.scheme, | 58 |
| abstract_inverted_index.Finally, | 80 |
| abstract_inverted_index.existing | 160 |
| abstract_inverted_index.expected | 45 |
| abstract_inverted_index.factors. | 79 |
| abstract_inverted_index.improves | 157 |
| abstract_inverted_index.measures | 7, 20, 40, 94 |
| abstract_inverted_index.process. | 17 |
| abstract_inverted_index.requires | 49 |
| abstract_inverted_index.samples. | 53 |
| abstract_inverted_index.setting. | 135 |
| abstract_inverted_index.spectral | 101 |
| abstract_inverted_index.variance | 68 |
| abstract_inverted_index.Markovian | 134 |
| abstract_inverted_index.extension | 84 |
| abstract_inverted_index.measures, | 103 |
| abstract_inverted_index.shortfall | 105 |
| abstract_inverted_index.variance, | 24 |
| abstract_inverted_index.$Ω(1/ε)$ | 161 |
| abstract_inverted_index.continuity | 98 |
| abstract_inverted_index.criterion, | 99 |
| abstract_inverted_index.discounted | 11, 144 |
| abstract_inverted_index.estimating | 5, 35, 125 |
| abstract_inverted_index.estimation | 87 |
| abstract_inverted_index.knowledge, | 112 |
| abstract_inverted_index.satisfying | 95 |
| abstract_inverted_index.truncation | 57 |
| abstract_inverted_index.$Ω(1/ε^2) | 155 |
| abstract_inverted_index.Conditional | 28 |
| abstract_inverted_index.estimation. | 69 |
| abstract_inverted_index.logarithmic | 78 |
| abstract_inverted_index.$Ω(1/ε^2)$ | 52 |
| abstract_inverted_index.Value-at-Risk | 25, 29 |
| abstract_inverted_index.utility-based | 104 |
| abstract_inverted_index.$ε$-accuracy, | 42 |
| abstract_inverted_index.high-probability | 47 |
| abstract_inverted_index.infinite-horizon | 10, 143 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |