arXiv:2405.17796

Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff

Jian Qian, Haichen Hu, David Simchi-Levi

제출 2024-05-28

원문 초록

Motivated by the recent discovery of a statistical and computational reduction from contextual bandits to offline regression (Simchi-Levi and Xu, 2021), we address the general (stochastic) Contextual Markov Decision Process (CMDP) problem with horizon H (as known as CMDP with H layers). In this paper, we introduce a reduction from CMDPs to offline density estimation under the realizability assumption, i.e., a model class M containing the true underlying CMDP is provided in advance. We develop an efficient, statistically near-optimal algorithm requiring only O(HlogT) calls to an offline density estimation algorithm (or oracle) across all T rounds of interaction. This number can be further reduced to O(HloglogT) if T is known in advance. Our results mark the first efficient and near-optimal reduction from CMDPs to offline density estimation without imposing any structural assumptions on the model class. A notable feature of our algorithm is the design of a layerwise exploration-exploitation tradeoff tailored to address the layerwise structure of CMDPs. Additionally, our algorithm is versatile and applicable to pure exploration tasks in reward-free reinforcement learning.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.02891v2cs.LG공통 태그 Multi-Armed Bandits

오분류 리덕션을 통한 비정상 선형 밴딧의 동적 후회

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

많은 온라인 의사결정 문제는 라운드별 실행 가능한 행동과 변화하는 보상 모델을 모두 수반한다. 적격 광고 노출, 실행 가능한 가격, 이용 가능한 치료법은 시간에 따라 바뀔 수 있고, 사용자 선호, 수요 곡선, 환자 반응은 진화할 수 있다. 이러한 응용에 동기를 받아 본 논문은 라운드별 실행 가능 의사결정 집합을 갖는 비정상 선형 밴딧을 연구한다. 핵심 기여는 비정상 선형 밴딧의 파라미터 드리프트를 맥락적 선형 밴딧의 모델 오지정과 연결하면서 라운드별 의사결정 기준을 보존하는 블록 단위 환원이다. 이 연결을 통해 오지정 적응형 학습을 활용하여 일반적인 시간 가변 의사결정 집합에 대한 동적 후회 보장을 얻을 수 있다. 경로 길이 예산 $P_T$가 알려진 경우, 비적응적 파라미터 경로 하에서 일반 컴팩트하고 적응적이며 비예측적인 의사결정 집합에 대해, 그리고 비적응적 환경 하에서 $K$-암 맥락적 선형 밴딧에 대해 이러한 보장을 확립한다. 일반 시간 가변 의사결정 집합에서 본 논문의 경계는 $T$와 $P_T$에 대한 의존성을 기존 LinUCB 기반 접근법에서 가능한 $\widetilde O(T^{3/4}P_T^{1/4})$ 보장에서 $\widetilde O(T^{2/3}P_T^{1/3})$로 개선하며, 이는 로그 인자를 제외하고 비정상 하한의 의존성과 일치한다.

arXiv:2606.17413v3cs.LG공통 태그 Density Estimation

라플라스 근사와 정규화 흐름을 활용한 심층 학습을 통한 OCO-2 스펙트럼에서의 대기 CO2 상각 확률적 검색

Amortized Probabilistic Retrieval of Atmospheric CO2 from OCO-2 Spectra Using Deep Learning with Laplace Approximations and Normalizing Flows

대기 중 이산화탄소(CO$_2$)의 우주 기반 관측은 전 지구 탄소 수지를 제약한다. NASA의 궤도 탄소 관측위성 2호(OCO-2)는 고해상도 스펙트럼으로부터 CO$_2$의 칼럼 평균 건조 공기 몰분율(XCO$_2$)을 추정하지만, 운용 중인 반演 방법은 계산 비용이 크고 반演된 사후분포에 엄격한 가우시안성 가정을 부과한다. 우리는 상각된 확률적 추론을 통해 이 두 문제를 모두 해결하는 딥러닝 프레임워크를 제시한다. 실제 관측에 대한 참값이 없으므로, 보정된 순방향 모형 오차를 갖는 고충실도 OCO-2 시뮬레이션 앙상블에서 학습하고 평가하며, 동일한 복사휘도에 대해 편향 보정을 적용하지 않은 버전 10 운용 완전 물리 반演과 비교한다. 우리의 아키텍처는 각 스펙트럼 대역을 별도로 인코딩하고, Laplace 근사와 조건부 정규화 흐름을 사용하여 전체 CO$_2$ 칼럼 또는 그 요약량의 사후분포를 추정한다. 일단 학습되면 추론 비용은 관측 한 건당 분 단위가 아니라 밀리초 단위이다. 순방향 모형 불일치를 명시적으로 포함하는 시뮬레이션으로 학습한 우리의 반演은 우리가 고려한 두 데이터 분할 모두에서 XCO$_2$에 대해 운용 반演보다 더 정확하며, 프로파일에서는 경쟁력이 있다. 흐름 모형은 가우시안이 표현할 수 없는 비대칭 사후분포를 표현하며, 이 이득은 규모가 아니라 형태에 기인하고, 예측 밀도에서의 이점은 정확도 이점이 사라진 곳에서도 지속된다. 이러한 결과는 육지 전용 앙상블에서 운용 알고리즘의 한 가지 구성에 대해 확립된 것이다. 보류된 기준 관측과 보지 못한 두 달에서도 XCO$_2$와 밀도의 이점이 지속된다. XCO$_2$의 경우 2월 데이터에서 커버리지가 명목값에 가까우며, 보지 못한 달들에서는 명목값에 미치지 못하지만 운용 반演의 경우보다 훨씬 더 명목값에 가깝다.

arXiv:2604.08116v3cs.CE공통 태그 Density Estimation

에너지 기반 모델을 위한 대조 학습, 중요도 샘플링, 브리지 샘플링의 통합적 관점

A unifying view of contrastive learning, importance sampling, and bridge sampling for energy-based models

지난 수십 년간 에너지 기반 모델(EBM)은 가능도의 한 구성 요소가 다루기 어려워 명시적으로 평가할 수 없는 확률 모델의 중요한 부류가 되었다. 따라서 EBM의 모수 추정은 기존 추론 방법으로는 어려운 과제이다. 본 연구는 이러한 다양한 방법론적 기여를 하나의 통합된 틀 안에 모은 리뷰 논문으로, EBM의 맥락에서 잡음 대조 추정(NCE), 역 로지스틱 회귀(RLR), Bennett의 수락비(BAR) 방법, 다중 중요도 샘플링(MIS), 브리지 샘플링 간의 연결을 강조한다. 이 중 일부는 특정 조건에서 서로 동등하다. 이러한 통합적 관점은 기존 방법들 간의 관계를 명확히 하고 새로운 추정량의 개발을 가능하게 하며, 통계적 및 계산적 효율성을 개선할 잠재력을 가진다. 더 나아가 본 연구는 NCE의 유연성과 강건성 측면에서의 성공을 설명하는 데 도움을 주는 동시에, 그 성능을 더 개선할 수 있는 상황도 식별한다. 우리의 목표는 명확하고 간결한 유도를 통해 이러한 기여를 공통의 틀 안에 모으고 주요 결과와 그 기저의 아이디어를 더 넓은 독자층이 이해할 수 있도록 하는, 자기완결적이고 접근하기 쉬운 서술을 제공하는 것이다. 기여는 두 가지이다. 첫째, 본 연구는 이 분야에 입문하는 연구자들을 위해 기본 개념과 유도를 소개하는 포괄적인 튜토리얼 역할을 한다. 둘째, 숙련된 실무자들에게 철저한 리뷰를 제공한다. 수치 실험에 사용된 코드는 결과의 재현성을 지원하기 위해 공개되어 있다.

arXiv:2604.12497v3cs.LG공통 태그 Multi-Armed Bandits

AI 기반 분석에서의 인간 감독 배분

Allocating Human Oversight in AI-Enabled Analytics

인공지능은 많은 분석 과제에 저비용 예측을 제공하지만, 그 신뢰성과 추가적인 사람 레이블의 가치는 과제마다 다르다. 본 연구는 과제 수준의 불확실성이 알려져 있지 않고 각 획득한 레이블이 추정과 이후의 할당 모두에 정보를 제공하는 상황에서, 공유된 사람 검증 예산을 어떻게 할당할 것인지를 연구한다. 난이도가 알려진 경우, 기준 방법은 과제의 중요도와 레이블 비용을 반영하는 비용 조정 Neyman 규칙을 따른다. 본 연구의 Tuned Rectification-Difficulty 프레임워크 내에서, 짝지어진 사람 레이블과 예측으로부터 조정된 예측 기반 추론(tuned prediction-powered inference)의 보정 계수와 그에 따른 난이도를 함께 학습하는 상한 신뢰 구간(upper-confidence-bound) 정책을 개발하고, 신뢰 반경 정책에 대한 할당 후회(allocation-regret) 보장을 증명한다. 합성 실험과 68개 과제 및 2,000명 이상의 응답자로 구성된 실제 디지털 트윈 설문에서, 본 방법은 할당 목적함수에 대해 오라클과의 격차 대부분을 좁힌다. 또한 균등 할당과 동일한 추정 오차를 각각 최대 22.7%, 4.5% 더 적은 사람 레이블로 달성한다. 동일한 할당 구조는 스칼라 잔차 분산을 스칼라화된 샌드위치 공분산으로 대체함으로써 스칼라 평균을 넘어 회귀 및 선택/컨조인트 추정을 포함한 벡터값 의사결정 모델로 확장된다. AI의 가치는 모델 정확도뿐 아니라 사람의 감독이 가장 필요한 곳에 이를 집중시키는 운영 정책에도 달려 있다.

arXiv:2605.24274v3cs.LG공통 태그 Density Estimation

입력 볼록 신경망 학습을 위한 리프트

A lift for input-convex neural net training

입력 볼록 신경망은 밀도 모델과 수송 사상의 볼록 포텐셜을 매개변수화하며, 그 볼록성을 위해서는 계층 간 가중치가 비음수여야 한다. 투영 경사 하강법은 매 단계 후 투영을 수행하여 이를 강제하는데, 미니배치 잡음 때문에 경계를 무한히 반복해서 넘나들게 되어 투영이 식별하지 못하는 활성 집합이 발생한다. 미분 가능한 대안인 직접 소프트플러스는 소프트플러스 양수화 사상을 통해 자유 잠재 가중치를 최적화한다. 해당 잠재 가중치가 0보다 훨씬 작은 곳에서는 사상의 도함수가 지수적으로 작아 기울기와 그 잡음을 모두 축소시킨다. 이 영역을 어깨(shoulder)라 부르며, 여기에 도달한 가중치는 거의 움직이지 않고 지수적으로 긴 시간 동안 머무른다. 본 연구는 자유 잠재 가중치를 학습 가능한 슬랙과, 학습 배치의 순열 불변 요약을 입력받는 하이퍼네트워크의 출력의 합으로 대체하는 리프트(lift)를 제안한다. 그러면 잠재 가중치가 기울기를 구성하는 바로 그 배치에 따라 변하므로 둘이 결합된다. 이러한 결합이 갱신의 분산에 1차로 한 항을 더함을 보이고, 슬랙, 배치 의존성, 공유 배치가 각각 이를 위해 필요함을 보인다. 결합이 손실 곡률과 양의 방향으로 정렬되는 경우, 어깨에 놓인 가중치는 전조건화 확률적 경사 하강법에서도 직접 소프트플러스보다 리프트에서 손실의 장벽을 더 빨리 넘는다. 여러 응용에서 리프트를 기존 두 방법과 비교한다. 직접 소프트플러스의 제약 가중치가 어깨에 도달하는 경우, 리프트는 직접 소프트플러스보다 목표를 더 가깝게 적합하며 같은 재구성 수준에 약 세 배 빨리 도달한다. 거의 어떤 가중치도 어깨에 도달하지 않는 경우에는 방법들이 서로 일치한다.

arXiv:2606.11711v2cs.LG공통 태그 Multi-Armed Bandits

용량 제약이 있는 지연 피드백 온라인 볼록 최적화

Capacity-Constrained Online Convex Optimization with Delayed Feedback

지연된 피드백을 갖는 온라인 학습은 일반적으로 학습자가 피드백이 도착할 때까지 보류 중인 모든 라운드를 추적할 수 있다고 가정한다. 실제로는 추적 자원이 유한하며, 추적할 수 없는 라운드의 피드백은 영구적으로 손실된다. 본 논문에서는 어느 시점에서든 최대 $C$개의 보류 라운드만 추적할 수 있는 엄격한 용량 제약 아래의 지연 온라인 볼록 최적화(OCO)를 연구한다. 지연 정보를 모형화하기 위해 선행 연구의 선견(clairvoyant) 가정을 정교화한 준선견(semi-clairvoyant) 모델을 도입한다. 이는 예측 시점에 지연을 알아야 한다고 요구하는 대신, 제약 없는 고전적 지연 설정과 마찬가지로 학습자가 지연 만료를 온라인으로 관측하도록 한다. 우리의 접근은 어느 라운드를 추적할지 무작위로 정하고 그 결과 관측값에 중요도 가중치를 부여하는 스케줄러를 사용하여, 새로운 ``지연 및 가중'' OCO 문제로 환원하는 방식으로 진행된다. 기본 문제에 대해 Delayed-Weighted FTRL과 그 밴딧 유사 알고리즘을 제안하고 분석하며, 두 설정 모두에서 가중치가 지연된 피드백과 어떻게 상호작용하는지 특성화하는 후회 한계를 얻는다. 이 한계를 스케줄러와 결합하면 볼록 및 강볼록 손실, 1차 및 밴딧 피드백 모두에 대해 용량 제약 OCO의 후회 보장을 얻는다. 1차 피드백에서는 용량 $C = \Omega(\log T)$이면 로그 인자를 제외하고 표준 지연 OCO 비율을 회복하기에 충분하다. 밴딧 피드백에서는 표준 지연 BCO 비율이 $(1 + \sigma_{\text{max}}/C)$ 인자로 조절되며, 여기서 $\sigma_{\text{max}}$는 미해결 관측의 최대 개수이다. 이로써 $C < \sigma_{\text{max}}$일 때에도 후회 한계가 점진적으로 나빠진다. 분석을 수치 실험으로 보완한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.