TCP 확인응답을 위한 동시 경쟁비 및 리그렛 보장
Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment
한국어 초록
본 연구는 TCP 확인응답(acknowledgment)에 대한 동시 경쟁비(competitive ratio) 및 리그렛(regret) 보장을 다룬다. 각 확인응답은 대기 중인 모든 패킷을 처리하며, 목표는 총 확인응답 비용과 대기 비용의 합을 최소화하는 것이다. 결정론적(deterministic) 온라인 알고리즘으로는 경쟁비 $2$보다 더 나은 성능을 달성할 수 없다는 것이 잘 알려져 있다. $k$개의 무작위화된(randomized) 온라인 전문가(expert)와 $0<\varepsilon<1$가 주어졌을 때, 우리는 실현된 총 비용이 오프라인 최적 비용 $\mathrm{OPT}$의 $(2+\varepsilon)$배를 항상 넘지 않으며, 실현 비용이 가장 작은 전문가에 대한 기대 리그렛이 $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$인 무작위화된 온라인 알고리즘을 구성한다. 이 알고리즘은 패킷 수나 $\mathrm{OPT}$에 대한 사전 지식을 요구하지 않는다. 우리의 알고리즘은 전문가 간 전환 비용(switching cost)을 제어하며, 허용된 경쟁비 한계와 현재 비용 사이의 격차를 이용하여 언제 학습할지를 결정한다. 또한 우리는 $k\ge 2$일 때 이 리그렛 한계가 $\mathrm{OPT}$, $k$, $\varepsilon$에 대해 점근적으로(asymptotically) 최적임을, 그리고 하위선형(sublinear) 리그렛을 위해서는 $\varepsilon>0$이 필요함을 보이는 하한(lower bound)을 증명한다.
원문 초록
We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than $2$. Given $k$ randomized online experts and $0<\varepsilon<1$, we construct a randomized online algorithm whose realized total cost is always at most $(2+\varepsilon)$ times the offline optimal cost $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{OPT}$. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for $k\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
배려적 선제: 지속적 공유 환경에서 장기 과업 계획 개선
Courteous Anticipation: Improving Long-Lived Task Planning in Persistent Shared Environments
동적 환경에서의 최적 계획 수립
Optimal Planning in a Dynamic World
배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.
DeliveryGym: An RL Environment for Long-Horizon Embodied Agent Planning with Adaptive Curriculum
The user asked for a JSON-only translation response with no markdown fences. Here is the result: {"title_ko": "DeliveryGym: 적응형 커리큘럼 기반 장기 체화 에이전트 계획을 위한 강화학습 환경", "abstract_ko": "실행 가능한 환경은 LLM 에이전트가 자신의 행동 결과로부터 학습할 수 있게 한다. 체화 에이전트의 경우, 그 결과는 현재 과제의 성공 여부를 넘어선다. 배달을 완료하는 것은 이후 작업에 필요한 시간, 에너지, 또는 돈을 소모할 수 있다. 따라서 계획 학습을 위해서는 이러한 의존성을 보존하고 완전한 궤적에 걸쳐 이를 피드백으로 전환하는 환경이 필요하다.\n\n우리는 연속적인 배달원 근무 교대를 대상으로 에이전트를 평가하고 학습하는 3D 환경인 DeliveryGym을 제안한다. 이는 다중 모달 도구 상호작용과 지속적인 세계 동역학을 결합하고, 시뮬레이터 이벤트로부터 궤적 보상을 계산하여 에이전트 결정의 비용을 강화학습(RL)에 사용할 수 있게 한다. 또한 평가는 고정한 채, 환경은 정책에서 관찰된 약점에 맞춰 향후 학습 교대를 적응시킨다.\n\n6개 모델과 13개 도시 맵에 걸쳐, 평가는 할당된 배달을 안정적으로 수행하는 것과 한 교대 동안 업무를 선택하고 순서를 정하는 것 사이의 격차를 드러낸다. 보지 못한 도시 테스트 세트에서 RL은 Qwen3-VL-4B의 순수익을 54.3% 향상시켜, 완전한 교대로부터 학습하면 이러한 결합된 제약 하에서 성능이 개선됨을 보여준다. 학습 환경을 적응시키면 100회 업데이트에서 균일 샘pling 대비 평가 수익이 18% 개선되어, 에이전트가 연습하는 상황이 무엇인지도 중요함을 시사한다. DeliveryGym은 에피소드 내에서 배달을 조율하고 이후 주문을 위해 자원을 보존하는 방법을 에이전트가 학습하는 과정을 연구할 수 있는 실행 가능한 설정을 제공한다."}
양자 클라우드 오케스트레이션에서 비용과 지연 트레이드오프를 위한 양자 강화학습
Quantum Reinforcement Learning for Cost and Delay Tradeoffs in Quantum Cloud Orchestration
양자-서비스(QaaS) 모델을 통해 제공되는 양자 클라우드 컴퓨팅은 양자 컴puting 자원에 대한 접근을 제공한다. 그러나 근본적으로 이질적인 양자 자원에 동일한 시간 기반 요금제를 적용하면, 특히 실행 비용과 시스템 성능 사이의 트레이드오프를 다룰 때 작업 오케스트레이션이 크게 복잡해진다. 휴리스틱 방법은 사전 정의된 스케줄링 규칙에 의존하는 반면, 고전적 심층 강화학습(DRL) 모델은 이 설정에서 더 많은 학습 가능 파라미터를 요구할 수 있다. 매개변수화 양자 회로(PQC)가 컴팩트한 함수 근사기로서 가질 잠재력에 착안하여, 우리는 PQC를 듀얼링 더블 심층 Q 네트워크(D3QN)와 통합해 비용과 지연을 동적으로 모두 반영하는 비용-지연 인식 양자 클라우드 스케줄링 프레임워크 QRLQ를 제안한다. 시뮬레이션 결과 QRLQ는 휴리스틱 기준선보다 더 낮은 평균 비용과 지연을 달성하며, 가용성 기반 및 회전 기반 휴리스틱 대비 평균 비용을 5–11% 낮추고, 가장 강한·약한 휴리스틱 기준선 대비 평균 지연을 각각 17% 및 82% 줄였다. 동시에 충실도 탐욕 정책 대비 실행 충실도를 2% 이내로 유지한다. 고전 DRL 기준선과 비교하면 QRLQ는 유사한 스케줄링 성능을 달성하면서 학습 가능 파라미터를 72% 더 적게 사용한다. 본 연구는 양자 클라우드 환경에서 작업 오케스트레이션에 양자 강화학습(QRL)을 사용하는 타당성을 탐구하고, 비용-지연 인식 양자 자원 관리의 잠재력을 보여준다.
ChronosAttack: LLM 에이전트를 대상으로 한 적대적 도구 스케줄링 공격
ChronosAttack: Adversarial Tool Scheduling Attacks on LLM Agents
대규모 언어 모델(LLM) 에이전트는 외부 도구 응답이 도착하는 대로 처리하는 경우가 많아, 응답 타이밍이 의사결정 과정의 일부가 됩니다. 본 연구에서는 정품 도구 응답을 수정, 추가, 제거하거나 앞당기지 않고 도착 시점만 변경하는 지연 전용 스케줄링 공격인 ChronosAttack을 소개합니다. 유계 지연(bounded delay)만으로도 동일한 증거의 제시 순서가 뒤바뀌어 최종 결정이 달라질 수 있습니다. 본 논문은 GPT-5.6 Sol, Gemini 3.6 Flash, DeepSeek V4 Flash, Claude Sonnet 4.6을 대상으로 ChronosAttack을 평가합니다. 취약한 환경에서 GPT-5.6 Sol과 Claude는 뚜렷한 목표 편향을 보였고, Gemini는 반대 방향으로 큰 편향을 나타냈으며, DeepSeek은 테스트된 스케줄 하에서 상대적으로 더 안정적이었습니다. 또한 순차적 에이전트 상태가 항상 필수적인 것은 아니며, 단 한 번의 스케줄링 역전만으로도 결정에 중대한 변화가 발생할 수 있음을 확인했습니다. 동기화 및 순서 일관성 방어 기법은 관찰 순서에 대한 공격자의 제어력을 줄여줍니다. 이러한 결과는 비동기 LLM 에이전트에서 도구 응답 타이밍 자체가 공격 표면이 될 수 있음을 보여줍니다.
정적·시간 가변 노출 하한을 갖는 불일치 반올림 공정 밴딧
Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
최소 노출 제약은 추천, 콘텐츠 큐레이션, 규제된 할당에서 각 공급자, arm, 또는 그룹이 집계적으로만이 아니라 기간 내에 보장된 노출을 받아야 할 때 발생한다. 우리는 정확한 노출 하한을 갖는 확률적 밴딧(stochastic bandits)을 연구하고, 핵심 대상은 반올림 문제임을 보인다. 분수 공정 스케줄이 정수 pull로 실현되며, 노출 오차는 정확히 불일치 벡터(discrepancy vector)이다. 주요 기여는 시간 가변 하한을 갖는 블록 단위 모델이다. BDQ-UCB는 모든 블록 하한을 결정적으로 만족하며, horizon $T$가 아닌 비필수 예산 $R$에 의해 지배되는 공정 regret을 갖고, 높은 확률에서 regret $O(\sqrt{KR\log(KT)})$를 달성한다. MOSS 잔차(residual) 변형은 $O(\sqrt{KR})$를 달성하고, 일치하는 하한이 양의 필수 노출(mandatory exposure)에서도 minimax rate $Θ(\sqrt{KR})$를 제공한다. kl-UCB$^{++}$ 잔차 규칙은 instance-dependent 최적성을 추가한다. 이 정식화는 겹치는 그룹 하한에 필수적이다. arm별 반올림은 그룹 크기에 대해 $Ω(s)$만큼 그룹 제약을 위반할 수 있는 반면, Beck--Fiala 영공(null-space) 반올림은 블록 예산 내에서 모든 그룹 하한을 만족하며 위반을 arm degree $t$ 미만으로 유지하고, 동일한 $R$-매개변수 regret과 UCB를 결합한다. 학습된 그룹 계획에 대해, 우리는 disjoint system을 $\widetildeΘ(\sqrt{KT})$에서 닫고, 겹침 하에서 naive index 규칙이 실패하는 이유를 설명하는 이중 원장(dual-ledger) 분해를 제시하며, 초기 cover-slack 조건 하에서 pathwise feasible한 plan-sampling 규칙을 증명하고 조건부 $\widetilde O(\sqrt{KT})$ 보장을 달성하되, 조건 없는 겹침 rate는 열어둔다. 합성 하한, MovieLens-100k 장르 노출, 배포 스트레스 테스트에 대한 실험은 penalty tuning 없이 정확한 feasibility를 보여주며, tuned Lagrangian baseline과 경쟁력 있는 regret을 보인다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
20 pages