서브메뉴
검색
Online Decision Making Via Linear Programming: Resource Allocation, Bandit Feedback, and Inverse Optimization
Online Decision Making Via Linear Programming: Resource Allocation, Bandit Feedback, and Inverse Optimization
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202104746
- ISBN
- 9798290652665
- DDC
- 741
- 저자명
- Sun, Chunlin.
- 서명/저자
- Online Decision Making Via Linear Programming: Resource Allocation, Bandit Feedback, and Inverse Optimization
- 발행사항
- [Sl] : Stanford University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 183 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-01, Section: A.
- 주기사항
- Advisor: Ye, Yinyu.
- 학위논문주기
- Thesis (Ph.D.)--Stanford University, 2025.
- 초록/해제
- 요약This dissertation investigates online learning and sequential decision-making under uncertainty, with a focus on algorithm design guided by the duality and optimality conditions of the corresponding offline optimization, or linear programming, problems. It presents both theoretical analyses and empirical results across three problem classes: (1) online resource allocation, (2) bandits with knapsacks, and (3) stochastic inverse optimization.For online resource allocation, we propose a simple and efficient algorithm that leverages the dual formulation of the offline problem. By approximating the dual optimal solution using a fast first-order method, the algorithm makes effective online decisions and achieves near-optimal performance with strong scalability.In the bandits with knapsacks setting, we introduce a novel primal-dual-based algorithm. By analyzing the structure of optimal decisions through the lens of optimality conditions, we design the first algorithm that achieves a problem-dependent logarithmic regret bound without requiring prior information.For stochastic inverse optimization, we address the challenge of learning a distribution over unobservable objective functions from observed optimal decisions. We develop a Bayesian algorithm that incorporates optimality conditions and provide the first theoretical guarantees in settings with a random objective.Overall, these results demonstrate how the duality and optimality conditions can guide online learning and sequential decision-making in various scenarios. The proposed methods offer both algorithmic and analytical insight into diverse problems.
- 일반주제명
- Design
- 일반주제명
- Linear programming
- 일반주제명
- Internet resources
- 일반주제명
- Distance learning
- 일반주제명
- Decision making
- 기타저자
- Stanford University.
- 기본자료저록
- Dissertations Abstracts International. 87-01A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017358747
■00520260202104746
■006m o d
■007cr#unu||||||||
■020 ▼a9798290652665
■035 ▼a(MiAaPQ)AAI32149751
■035 ▼a(MiAaPQ)Stanfordyc956yr0074
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a741
■1001 ▼aSun, Chunlin.
■24510▼aOnline Decision Making Via Linear Programming: Resource Allocation, Bandit Feedback, and Inverse Optimization
■260 ▼a[Sl]▼bStanford University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a183 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-01, Section: A.
■500 ▼aAdvisor: Ye, Yinyu.
■5021 ▼aThesis (Ph.D.)--Stanford University, 2025.
■520 ▼aThis dissertation investigates online learning and sequential decision-making under uncertainty, with a focus on algorithm design guided by the duality and optimality conditions of the corresponding offline optimization, or linear programming, problems. It presents both theoretical analyses and empirical results across three problem classes: (1) online resource allocation, (2) bandits with knapsacks, and (3) stochastic inverse optimization.For online resource allocation, we propose a simple and efficient algorithm that leverages the dual formulation of the offline problem. By approximating the dual optimal solution using a fast first-order method, the algorithm makes effective online decisions and achieves near-optimal performance with strong scalability.In the bandits with knapsacks setting, we introduce a novel primal-dual-based algorithm. By analyzing the structure of optimal decisions through the lens of optimality conditions, we design the first algorithm that achieves a problem-dependent logarithmic regret bound without requiring prior information.For stochastic inverse optimization, we address the challenge of learning a distribution over unobservable objective functions from observed optimal decisions. We develop a Bayesian algorithm that incorporates optimality conditions and provide the first theoretical guarantees in settings with a random objective.Overall, these results demonstrate how the duality and optimality conditions can guide online learning and sequential decision-making in various scenarios. The proposed methods offer both algorithmic and analytical insight into diverse problems.
■590 ▼aSchool code: 0212.
■650 4▼aDesign
■650 4▼aLinear programming
■650 4▼aInternet resources
■650 4▼aDistance learning
■650 4▼aDecision making
■690 ▼a0389
■71020▼aStanford University.
■7730 ▼tDissertations Abstracts International▼g87-01A.
■790 ▼a0212
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358747▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
