arXiv:2411.13993

Market Making without Regret

Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak

제출 2024-11-21

원문 초록

We consider a sequential decision-making setting where, at every round $t$, a market maker posts a bid price $B_t$ and an ask price $A_t$ to an incoming trader (the taker) with a private valuation for one unit of some asset. If the trader's valuation is lower than the bid price, or higher than the ask price, then a trade (sell or buy) occurs. If a trade happens at round $t$, then letting $M_t$ be the market price (observed only at the end of round $t$), the maker's utility is $M_t - B_t$ if the maker bought the asset, and $A_t - M_t$ if they sold it. We characterize the maker's regret with respect to the best fixed choice of bid and ask pairs under a variety of assumptions (adversarial, i.i.d., and their variants) on the sequence of market prices and valuations. Our upper bound analysis unveils an intriguing connection relating market making to first-price auctions and dynamic pricing. Our main technical contribution is a lower bound for the i.i.d. case with Lipschitz distributions and independence between prices and valuations. The difficulty in the analysis stems from the unique structure of the reward and feedback functions, allowing an algorithm to acquire information by graduating the "cost of exploration" in an arbitrary way.

함께 살펴볼 논문

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

arXiv:2607.20289v2cs.RO공통 태그 Sequential Decision Making

배려적 선제: 지속적 공유 환경에서 장기 과업 계획 개선

Courteous Anticipation: Improving Long-Lived Task Planning in Persistent Shared Environments

본 논문은 지속적인 환경을 공유하는 로봇들이 보류된(held-out) 시퀀스로부터 한 번에 하나씩 과업을 할당받는 과업 계획 시나리오를 다룬다. 표준 과업 계획기는 미래 과업에 대한 예측이 없고 다른 로봇의 제약을 고려하지 않으므로 각 과업을 독립적으로 해결하여, 모든 로봇의 미래 비용을 증가시키는 종료 상태를 남기며, 이러한 부작용은 긴 과업 시퀀스에서 누적된다. 시퀀스 전체의 비용을 줄이려면 로봇은 현재의 행동이 환경을 공유하는 모든 로봇의 미래 과업 수행에 어떤 영향을 미칠지 예측해야 한다. 이에 본 논문은 모델 기반 계획기가 후보 계획을 제안하고, 로봇별로 독립적으로 학습된 추정기를 통해 추정한 즉각적 비용과 모든 로봇에 대한 집계된 기대 미래 비용을 함께 최소화하는 계획을 선택하는 배려형 예측 계획(courteous anticipatory planning)을 제시한다. 이러한 분해된 정식화는 조합적인 공동 롤아웃을 피하고 모듈식 배치를 지원하며, 로봇을 추가하려면 해당 로봇의 추정기만 훈련하면 된다. 비슷한 능력을 갖지만 책임이 다른 로봇들이 있는 가정 환경과, 로봇들의 서로 다른 능력으로 인해 다른 로봇이 해결할 수 없는 상태가 만들어지는 레스토랑 환경이라는 두 가지 지속적 PDDL 도메인에서 평가한다. 긴 과업 시퀀스에서 본 계획기는 2대 로봇 가정 환경에서 근시안적 계획 대비 총비용을 10.4%, 이기적 예측 계획 대비 4.5% 줄였으며, 3대 로봇 레스토랑 환경에서는 각각 20.5%와 6.7% 줄였다.

arXiv:2610.10857v2cs.AI공통 태그 Sequential Decision Making

호라이즌 불변 행동 복제를 위한 자기 지도 키프레임 발견

Self-Supervised Keyframe Discovery for Horizon-Invariant Behavior Cloning

비마르코프 환경에서의 행동 복제(BC)는 정책이 장기 지평에 걸친 문맥 정보를 추론해야 하므로 어려운 문제이다. 기존 정책 아키텍처는 장기 의존성을 포착하기 위해 순환 또는 어텐션 기반 메커니즘에 의존한다. 그러나 순환 모델은 시간에 대한 역전파에서 은닉 상태 붕괴와 기울기 불안정성을 겪으며, 어텐션 기반 모델은 근본적으로 문맥 길이에 의해 제한된다. 이러한 문제를 해결하기 위해 본 논문은 무작위로 추출한 과거 관측으로부터 목적 함수를 학습하고 이를 키프레임 선택의 보상으로 사용하여 정보상 핵심적인 관측 집합($\textit{mnemonics}$)을 $\textit{발견}$하는 새로운 자기지도 방법인 Keyframe Mnemonics를 제안한다. 이후 발견된 키프레임을 조건으로 하는 BC 정책을 학습하여 행동 분포를 모델링한다. 단순성 편향 가정 하에서, 본 정식화는 정책의 작업 기억에 의사결정과 관련된 소수의 키프레임만을 유지하면서도 무한 지평에 걸친 문맥 유지 보장을 제공한다. 합성 기억 도메인에서 평가한 결과, mnemonic 조건부 BC 정책은 $100$%의 성공률(SR)을 달성하고 성능 저하 없이 학습 지평을 수 자릿수 넘어서는 지평으로 일반화한다. 또한 기억 집약적인 로봇 조작 벤치마크에서 $23$개 과제에 걸쳐 가장 강력한 기준선 대비 평균 절대 SR이 $13.9$% 향상되었다. 마지막으로 실제 로봇에서 $20\times$ 더 긴 시간 지평에서도 $80$%의 SR로 일반화됨을 보인다. 코드와 영상은 https://keyframe-mnemonics.github.io 에서 확인할 수 있다.

arXiv:2607.09993v2cs.GT공통 태그 Sequential Decision Making

베이지안 내쉬를 넘어서: 비대칭 정보 하의 적대적 팀 게임을 위한 미니맥스-후회 균형 학습

Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

적대적 경로 탐색, 목표 탐색, 그래프 상의 도달 가능성 게임과 같이 비대칭 정보가 존재하는 적대적 팀 게임(ATG)은 숨겨진 목표 깃발과 같은 은닉된 상대 유형과 기만에 강건한 전략을 요구한다. 비대칭 정보 하에서 기만은 전지적 상대가 자연(Nature)과 공모하여 관찰된 유형에 따라 행동을 조정할 수 있도록 유형 분포를 전략적으로 이동시키는 것으로 간주된다. 베이지안 내시 균형(BNE)과 같은 기존의 위험 중립 해 개념은 분포 이동에 민감하며, 분포적으로 강건한 접근법은 미리 정해진 모호성 집합 내에서만 보장을 제공한다. 이러한 한계를 해결하기 위해 본 연구는 미니맥스 후회 추론의 분포 비의존적 강건성과 명목 유형 분포의 확률적 정보를 결합한 새로운 균형 개념인 확률적 강건 미니맥스 후회 균형(PR-MRE)을 도입한다. PR-MRE는 유형 공간의 고신뢰도 부분집합에 대해 최악의 경우 후회를 최소화하여, 확률 질량의 전략적 재분배에 대한 보호를 제공하면서 완전히 분포 비의존적인 접근법의 보수성을 피한다. 유한 정규형 베이지안 게임에서 근사 PR-MRE 계산을 강건 쌍선형 계획법으로 정식화할 수 있음을 보이고, 계산 가능한 반정부호 완화를 유도한다. 이어서 이 완화를 강건 이중 오라클 프레임워크 내의 새로운 메타 솔버인 PRMRE-PSRO로 적응시켜, 심층 강화학습 최선 응답을 통해 근사 PR-MRE 전략을 집단 기반으로 학습할 수 있게 한다. 그래프 구조의 적대적 팀 게임에서의 실험은 PR-MRE가 위험 중립 베이지안 내시 균형 해에 비해 숨겨진 유형 전반에서 최악의 경우 성능이 크게 향상된 전략을 발견하며, 그 결과 전략적 분포 이동 하에서 더 강건한 행동을 보임을 입증한다.

arXiv:2610.01834v3cs.AI공통 태그 Sequential Decision Making

시뮬레이션은 코드가 담당하고, 평가는 Jev가 담당한다

Code Owns the Simulation, Jev Owns the Evaluation

Jev와 같은 판단 모델(judgment model)은 단 한 번의 호출로 추론 텍스트 없이 설명된 각 선택지에 대한 확률을 반환합니다. 이러한 특징 덕분에 에이전트의 행동 선택 층(layer)으로서 매력적이지만, 어떤 결정을 신뢰할 수 있는지는 명확하지 않습니다. 본 연구에서는 인지 반사 테스트, 일회성 행렬 게임, 텍스트 게임 ALFWorld 및 로봇 제어에서 Jev를 테스트하고 뚜렷한 경계를 발견했습니다. Jev는 입력에 설명된 내용으로부터 올바른 선택지를 판단할 수 있을 때 성공하며, 이를 본 연구에서는 평가(evaluation)라고 부릅니다. 구체적으로, Jev는 직관에 반하는 인지 반사 테스트(Cognitive Reflection Test) 문제의 99%를 해결합니다. 그러나 올바른 선택지가 상대방의 행동이나 먼저 달성해야 하는 하위 목표와 같이 시뮬레이션(simulation, 즉 입력에 없는 내용을 예측하는 것)에 의존할 때는 실패합니다. 게임에서 Jev는 상대방의 행동이 주어지지 않기 때문에 합리적인 상대가 무작위로 행동하는 것처럼 차선으로 플레이합니다. ALFWorld에서 Jev는 작업 설명에 언급된 사물이나 장소를 지칭하는 명령을 선호합니다. 예를 들어, "서랍에 깨끗한 칼을 넣어라"라는 작업이 주어지면, Jev는 싱크대에서 칼을 먼저 씻는 대신 씻지 않은 칼을 서랍으로 곧장 가져갑니다. 놀랍게도 이러한 실패 중 다수는 지식의 부족 때문이 아닙니다. 상대가 무엇을 할지 별도로 질문을 받으면 Jev는 대개 정확하게 답하며, 상대의 행동이 주어지면 적절하게 대응합니다. Jev가 실패하는 것은 단 한 번의 호출로 시뮬레이션을 수행하고 이에 기반한 평가까지 동시에 처리해야 할 때입니다. 이는 예측이나 시뮬레이션을 코드가 수행하도록 할 것을 시사합니다. ALFWorld의 미리보기(lookahead)나 로봇 제어의 물리 시뮬레이션과 같이 코드가 이를 제공하면, Jev는 일반적인 평가 능력을 통해 전문가 수준의 제어기가 됩니다.

arXiv:2607.13686v2cs.LG공통 태그 Sequential Decision Making

일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

본 논문은 맥락적 조합 세미밴딧(CCSB) 문제를 연구한다. 이 문제에서 학습자는 매 라운드마다 맥락을 관측하고, 기본 팔들의 부분집합으로 이루어진 조합 행동을 선택하며, 선택된 각 팔의 보상을 받는다. 목표는 시간에 따른 누적 보상을 최대화하는 것이다. 기존의 많은 연구가 선형 보상 함수 근사를 갖는 CCSB 문제에 초점을 맞춘 반면, 일반 보상 함수 근사를 갖는 CCSB 문제에 대한 효율적인 알고리즘 설계는 제한적이다. 본 연구에서는 학습자가 참 보상 함수를 포함하는 보상 함수 클래스 $\mathcal{F}$에 접근할 수 있는 실현 가능(realizable) 설정을 연구하고 $\mathrm{SquareCB{.}Comb}$ 알고리즘을 제안한다. $\mathrm{SquareCB{.}Comb}$가 $O(\sqrt{m A T \log |\mathcal{F}|})$의 미니맥스 최적 후회 한계를 달성함을 증명한다. 여기서 $A$는 팔의 수, $m$은 조합 행동에 포함되는 팔의 최대 개수, $T$는 시간 지평이다. 또한 맥락이 주어졌을 때 모든 팔의 보상을 효율적으로 예측할 수 있는 온라인 회귀 오라클이 있고, 조합 행동 집합이 효율적인 선형 최적화 또는 팔에 대한 임의의 목표 주변 확률이 주어졌을 때의 효율적인 샘플링 중 하나를 허용하면 $\mathrm{SquareCB{.}Comb}$는 계산적으로 효율적이다. 웹페이지 추천과 맥락적 최단 경로 문제에서 알고리즘의 효과를 실험적으로 검증한다.

arXiv:2610.10942v2cs.AI공통 태그 Sequential Decision Making

StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경

StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents

강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.

토론

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