Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming Article Swipe
Wenzhi Gao
,
Dongdong Ge
,
Chenyu Xue
,
Chunlin Sun
,
Yinyu Ye
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2501.02761
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2501.02761
Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical success of first-order methods, they typically achieve a regret no better than $\mathcal{O} ( \sqrt{T} )$, which is suboptimal compared to the $\mathcal{O} (\log T)$ bound guaranteed by the state-of-the-art linear programming (LP)-based online algorithms. This paper establishes a general framework that improves upon the $\mathcal{O} ( \sqrt{T} )$ result when the LP dual problem exhibits certain error bound conditions. For the first time, we show that first-order learning algorithms achieve $o( \sqrt{T} )$ regret in the continuous support setting and $\mathcal{O} (\log T)$ regret in the finite support setting beyond the non-degeneracy assumption. Our results significantly improve the state-of-the-art regret results and provide new insights for sequential decision-making.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2501.02761
- https://arxiv.org/pdf/2501.02761
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4406122774
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4406122774Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2501.02761Digital Object Identifier
- Title
-
Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear ProgrammingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-01-06Full publication date if available
- Authors
-
Wenzhi Gao, Dongdong Ge, Chenyu Xue, Chunlin Sun, Yinyu YeList of authors in order
- Landing page
-
https://arxiv.org/abs/2501.02761Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2501.02761Direct 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/2501.02761Direct OA link when available
- Concepts
-
Regret, Decoupling (probability), Online learning, Linear programming, Computer science, Combinatorics, Discrete mathematics, Mathematics, Mathematical optimization, Algorithm, Engineering, Machine learning, World Wide Web, Control engineeringTop 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/W4406122774 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2501.02761 |
| ids.doi | https://doi.org/10.48550/arxiv.2501.02761 |
| ids.openalex | https://openalex.org/W4406122774 |
| fwci | |
| type | preprint |
| title | Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12101 |
| topics[0].field.id | https://openalex.org/fields/18 |
| topics[0].field.display_name | Decision Sciences |
| topics[0].score | 0.9610999822616577 |
| topics[0].domain.id | https://openalex.org/domains/2 |
| topics[0].domain.display_name | Social Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1803 |
| topics[0].subfield.display_name | Management Science and Operations Research |
| topics[0].display_name | Advanced Bandit Algorithms Research |
| topics[1].id | https://openalex.org/T11182 |
| topics[1].field.id | https://openalex.org/fields/18 |
| topics[1].field.display_name | Decision Sciences |
| topics[1].score | 0.9524000287055969 |
| 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 | Auction Theory and Applications |
| topics[2].id | https://openalex.org/T12072 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9366999864578247 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Machine Learning and Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C50817715 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8931270837783813 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q79895177 |
| concepts[0].display_name | Regret |
| concepts[1].id | https://openalex.org/C205606062 |
| concepts[1].level | 2 |
| concepts[1].score | 0.838955819606781 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q5249645 |
| concepts[1].display_name | Decoupling (probability) |
| concepts[2].id | https://openalex.org/C2986087404 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5842352509498596 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q15946010 |
| concepts[2].display_name | Online learning |
| concepts[3].id | https://openalex.org/C41045048 |
| concepts[3].level | 2 |
| concepts[3].score | 0.47091054916381836 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q202843 |
| concepts[3].display_name | Linear programming |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.45739516615867615 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C114614502 |
| concepts[5].level | 1 |
| concepts[5].score | 0.44450801610946655 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[5].display_name | Combinatorics |
| concepts[6].id | https://openalex.org/C118615104 |
| concepts[6].level | 1 |
| concepts[6].score | 0.37016114592552185 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[6].display_name | Discrete mathematics |
| concepts[7].id | https://openalex.org/C33923547 |
| concepts[7].level | 0 |
| concepts[7].score | 0.36387312412261963 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[7].display_name | Mathematics |
| concepts[8].id | https://openalex.org/C126255220 |
| concepts[8].level | 1 |
| concepts[8].score | 0.32899412512779236 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[8].display_name | Mathematical optimization |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.2962741553783417 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C127413603 |
| concepts[10].level | 0 |
| concepts[10].score | 0.1384788453578949 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[10].display_name | Engineering |
| concepts[11].id | https://openalex.org/C119857082 |
| concepts[11].level | 1 |
| concepts[11].score | 0.13752001523971558 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q2539 |
| concepts[11].display_name | Machine learning |
| concepts[12].id | https://openalex.org/C136764020 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0774475634098053 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q466 |
| concepts[12].display_name | World Wide Web |
| concepts[13].id | https://openalex.org/C133731056 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q4917288 |
| concepts[13].display_name | Control engineering |
| keywords[0].id | https://openalex.org/keywords/regret |
| keywords[0].score | 0.8931270837783813 |
| keywords[0].display_name | Regret |
| keywords[1].id | https://openalex.org/keywords/decoupling |
| keywords[1].score | 0.838955819606781 |
| keywords[1].display_name | Decoupling (probability) |
| keywords[2].id | https://openalex.org/keywords/online-learning |
| keywords[2].score | 0.5842352509498596 |
| keywords[2].display_name | Online learning |
| keywords[3].id | https://openalex.org/keywords/linear-programming |
| keywords[3].score | 0.47091054916381836 |
| keywords[3].display_name | Linear programming |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.45739516615867615 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/combinatorics |
| keywords[5].score | 0.44450801610946655 |
| keywords[5].display_name | Combinatorics |
| keywords[6].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[6].score | 0.37016114592552185 |
| keywords[6].display_name | Discrete mathematics |
| keywords[7].id | https://openalex.org/keywords/mathematics |
| keywords[7].score | 0.36387312412261963 |
| keywords[7].display_name | Mathematics |
| keywords[8].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[8].score | 0.32899412512779236 |
| keywords[8].display_name | Mathematical optimization |
| keywords[9].id | https://openalex.org/keywords/algorithm |
| keywords[9].score | 0.2962741553783417 |
| keywords[9].display_name | Algorithm |
| keywords[10].id | https://openalex.org/keywords/engineering |
| keywords[10].score | 0.1384788453578949 |
| keywords[10].display_name | Engineering |
| keywords[11].id | https://openalex.org/keywords/machine-learning |
| keywords[11].score | 0.13752001523971558 |
| keywords[11].display_name | Machine learning |
| keywords[12].id | https://openalex.org/keywords/world-wide-web |
| keywords[12].score | 0.0774475634098053 |
| keywords[12].display_name | World Wide Web |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2501.02761 |
| 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/2501.02761 |
| 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/2501.02761 |
| locations[1].id | doi:10.48550/arxiv.2501.02761 |
| 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.2501.02761 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5084921662 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-0167-7868 |
| authorships[0].author.display_name | Wenzhi Gao |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Gao, Wenzhi |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5054490752 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Dongdong Ge |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ge, Dongdong |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5103131947 |
| authorships[2].author.orcid | https://orcid.org/0009-0004-6695-8147 |
| authorships[2].author.display_name | Chenyu Xue |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Xue, Chenyu |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5102394177 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Chunlin Sun |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Sun, Chunlin |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5034741427 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Yinyu Ye |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Ye, Yinyu |
| authorships[4].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/2501.02761 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12101 |
| primary_topic.field.id | https://openalex.org/fields/18 |
| primary_topic.field.display_name | Decision Sciences |
| primary_topic.score | 0.9610999822616577 |
| primary_topic.domain.id | https://openalex.org/domains/2 |
| primary_topic.domain.display_name | Social Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1803 |
| primary_topic.subfield.display_name | Management Science and Operations Research |
| primary_topic.display_name | Advanced Bandit Algorithms Research |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2971351794, https://openalex.org/W4376155396, https://openalex.org/W1947085858, https://openalex.org/W2174986909, https://openalex.org/W2527791220, https://openalex.org/W2101991911, https://openalex.org/W2155070487, https://openalex.org/W4311589891, https://openalex.org/W3041944716 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2501.02761 |
| 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/2501.02761 |
| 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/2501.02761 |
| primary_location.id | pmh:oai:arXiv.org:2501.02761 |
| 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/2501.02761 |
| 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/2501.02761 |
| publication_date | 2025-01-06 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.( | 42, 75 |
| abstract_inverted_index.a | 36, 67 |
| abstract_inverted_index.)$ | 77, 102 |
| abstract_inverted_index.LP | 81 |
| abstract_inverted_index.an | 4 |
| abstract_inverted_index.by | 56 |
| abstract_inverted_index.in | 7, 104, 114 |
| abstract_inverted_index.is | 46 |
| abstract_inverted_index.no | 38 |
| abstract_inverted_index.of | 30 |
| abstract_inverted_index.on | 19 |
| abstract_inverted_index.to | 49 |
| abstract_inverted_index.we | 93 |
| abstract_inverted_index.$o( | 100 |
| abstract_inverted_index.)$, | 44 |
| abstract_inverted_index.For | 89 |
| abstract_inverted_index.Our | 123 |
| abstract_inverted_index.T)$ | 53, 112 |
| abstract_inverted_index.and | 11, 14, 109, 131 |
| abstract_inverted_index.for | 135 |
| abstract_inverted_index.has | 17 |
| abstract_inverted_index.new | 133 |
| abstract_inverted_index.the | 27, 50, 57, 73, 80, 90, 105, 115, 120, 127 |
| abstract_inverted_index.This | 64 |
| abstract_inverted_index.both | 8 |
| abstract_inverted_index.dual | 82 |
| abstract_inverted_index.role | 6 |
| abstract_inverted_index.show | 94 |
| abstract_inverted_index.than | 40 |
| abstract_inverted_index.that | 70, 95 |
| abstract_inverted_index.they | 33 |
| abstract_inverted_index.upon | 72 |
| abstract_inverted_index.when | 79 |
| abstract_inverted_index.(\log | 52, 111 |
| abstract_inverted_index.bound | 54, 87 |
| abstract_inverted_index.error | 86 |
| abstract_inverted_index.first | 91 |
| abstract_inverted_index.paper | 65 |
| abstract_inverted_index.plays | 3 |
| abstract_inverted_index.time, | 92 |
| abstract_inverted_index.which | 45 |
| abstract_inverted_index.Online | 0 |
| abstract_inverted_index.better | 39 |
| abstract_inverted_index.beyond | 119 |
| abstract_inverted_index.finite | 116 |
| abstract_inverted_index.linear | 1, 59 |
| abstract_inverted_index.online | 23, 62 |
| abstract_inverted_index.recent | 15 |
| abstract_inverted_index.regret | 37, 103, 113, 129 |
| abstract_inverted_index.result | 78 |
| abstract_inverted_index.Despite | 26 |
| abstract_inverted_index.achieve | 35, 99 |
| abstract_inverted_index.certain | 85 |
| abstract_inverted_index.focused | 18 |
| abstract_inverted_index.general | 68 |
| abstract_inverted_index.improve | 126 |
| abstract_inverted_index.problem | 83 |
| abstract_inverted_index.provide | 132 |
| abstract_inverted_index.results | 124, 130 |
| abstract_inverted_index.revenue | 9 |
| abstract_inverted_index.setting | 108, 118 |
| abstract_inverted_index.success | 29 |
| abstract_inverted_index.support | 107, 117 |
| abstract_inverted_index.\sqrt{T} | 43, 76, 101 |
| abstract_inverted_index.compared | 48 |
| abstract_inverted_index.exhibits | 84 |
| abstract_inverted_index.improves | 71 |
| abstract_inverted_index.insights | 134 |
| abstract_inverted_index.learning | 24, 97 |
| abstract_inverted_index.methods, | 32 |
| abstract_inverted_index.research | 16 |
| abstract_inverted_index.resource | 12 |
| abstract_inverted_index.efficient | 21 |
| abstract_inverted_index.empirical | 28 |
| abstract_inverted_index.framework | 69 |
| abstract_inverted_index.important | 5 |
| abstract_inverted_index.typically | 34 |
| abstract_inverted_index.(LP)-based | 61 |
| abstract_inverted_index.algorithms | 98 |
| abstract_inverted_index.continuous | 106 |
| abstract_inverted_index.developing | 20 |
| abstract_inverted_index.guaranteed | 55 |
| abstract_inverted_index.management | 10 |
| abstract_inverted_index.sequential | 136 |
| abstract_inverted_index.suboptimal | 47 |
| abstract_inverted_index.algorithms. | 25, 63 |
| abstract_inverted_index.allocation, | 13 |
| abstract_inverted_index.assumption. | 122 |
| abstract_inverted_index.conditions. | 88 |
| abstract_inverted_index.establishes | 66 |
| abstract_inverted_index.first-order | 22, 31, 96 |
| abstract_inverted_index.programming | 2, 60 |
| abstract_inverted_index.$\mathcal{O} | 41, 51, 74, 110 |
| abstract_inverted_index.significantly | 125 |
| abstract_inverted_index.non-degeneracy | 121 |
| abstract_inverted_index.decision-making. | 137 |
| abstract_inverted_index.state-of-the-art | 58, 128 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |