{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/112101"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/112101","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms","abstract":"We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.","abstract_html":"We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.","abstract_has_math":true,"creators":["Zhang, Xiangyu"],"institution":"Cornell University","degree_name":"Ph. D., Operations Research and Information Engineering","degree_level":"Doctor of Philosophy","degree_discipline":"Operations Research and Information Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Frazier, Peter"],"committee_members":["Chen, Yudong","Dai, Jim","Topaloglu, Huseyin"],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-11-19T03:10:05Z","subjects":[],"languages":["en"],"rights":["Attribution-ShareAlike 4.0 International"],"rights_urls":["https://creativecommons.org/licenses/by-sa/4.0/"],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/pq7v-tc78"],"render_values":[{"text":"https://doi.org/10.7298/pq7v-tc78","href":"https://doi.org/10.7298/pq7v-tc78","code":true}]},{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["15578911"],"render_values":[{"text":"15578911","href":null,"code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 13180","ProQuest Publication ID: 29261579"],"render_values":[{"text":"ProQuest Submission ID: 13180","href":null,"code":true},{"text":"ProQuest Publication ID: 29261579","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/112101","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/112101","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F112101","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Frazier, Peter"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Chen, Yudong","Dai, Jim","Topaloglu, Huseyin"]},{"key":"dc:creator","label":"Author","values":["Zhang, Xiangyu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-10-31T16:21:16Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-10-31T16:21:16Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-08"]},{"key":"dc:relation.uri","label":"Dc Relation URI","values":["https://newcatalog.library.cornell.edu/catalog/15578911"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Operations Research and Information Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Operations Research and Information Engineering"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution-ShareAlike 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by-sa/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["15578911"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/pq7v-tc78"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["ProQuest Submission ID: 13180","ProQuest Publication ID: 29261579"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/112101"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"633c2716-ea3b-4032-9ed3-267b56825bdc\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2022-08</PublicationDate> <DOI>https://doi.org/10.7298/pq7v-tc78</DOI> <Authors> <Author> <DisplayName>Zhang, Xiangyu</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <License>https://creativecommons.org/licenses/by-sa/4.0/</License> <Abstract>We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Zhang, Xiangyu"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description","label":"Description","values":["155 pages"]},{"key":"dc:description.abstract","label":"Abstract","values":["We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dcterms:license","label":"Dcterms License","values":["https://hdl.handle.net/1813/59810.2"]},{"key":"dc:title","label":"Title","values":["Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"633c2716-ea3b-4032-9ed3-267b56825bdc\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2022-08</PublicationDate> <DOI>https://doi.org/10.7298/pq7v-tc78</DOI> <Authors> <Author> <DisplayName>Zhang, Xiangyu</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <License>https://creativecommons.org/licenses/by-sa/4.0/</License> <Abstract>We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Zhang, Xiangyu"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Frazier, Peter"],"dc:contributor.committeemember":["Chen, Yudong","Dai, Jim","Topaloglu, Huseyin"],"dc:creator":["Zhang, Xiangyu"],"dc:date.accessioned":["2022-10-31T16:21:16Z"],"dc:date.available":["2022-10-31T16:21:16Z"],"dc:date.issued":["2022-08"],"dc:description":["155 pages"],"dc:description.abstract":["We consider multi-action restless bandits with multiple resource constraints, also referred to as weakly coupled Markov decision processes. This problem is important in recommender systems, active learning, revenue management, and many other areas. An optimal policy can be theoretically found by solving a Markov decision process, but the computation required scales exponentially in the number of arms $N$. Thus, scalable approximate policies are important for problems with large $N$. We study the optimality gap, i.e., the loss in expected performance vs. that of the optimal policy, of such scalable policies. The tightest previous theoretical bounds, which apply only for a handful of carefully-designed policies, show that this optimality gap is $O(\\sqrt{N})$ for the finite-horizon case and $o(N)$ for the infinite-horizon case. This dissertation significantly improves these bounds by characterizing a much wider class of novel practically-computable policiesfor which the optimality gap is $O(\\sqrt{N})$ for both finite- and infinite-horizon restless bandits. Furthermore, for the finite-horizon case including time-varying environmental variables that affect transitions and rewards, we characterize a non-degeneracy condition under which the optimality gap is surprisingly $O(1)$. We demonstrate that our policies offer state-of-the-art empirical performance in numerical experiments."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["15578911"],"dc:identifier.doi":["https://doi.org/10.7298/pq7v-tc78"],"dc:identifier.other":["ProQuest Submission ID: 13180","ProQuest Publication ID: 29261579"],"dc:identifier.uri":["https://hdl.handle.net/1813/112101"],"dc:language.iso":["en"],"dc:relation.uri":["https://newcatalog.library.cornell.edu/catalog/15578911"],"dc:rights":["Attribution-ShareAlike 4.0 International"],"dc:rights.uri":["https://creativecommons.org/licenses/by-sa/4.0/"],"dcterms:license":["https://hdl.handle.net/1813/59810.2"],"dc:title":["Near-Optimality for Multi-action Multi-resource Restless Bandits with Many Arms"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Operations Research and Information Engineering"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Operations Research and Information Engineering"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:10:05Z"}