Otimização Convexa Online Com Restrições Variáveis no Tempo e Feedback de Bandit

Neste artigo, o problema de otimização convexa online com restrições variáveis no tempo é estudado do ponto de vista de um agente que toma ações sequenciais. Tanto a função objetivo quanto as funções de restrição são dinâmicas e desconhecidas a priori para o agente. Primeiro, consideramos o cenário do feedback do gradiente, em que os valores e gradientes da função objetivo e das funções de restrição na ação escolhida são revelados após a submissão de uma ação. Propomos um algoritmo online computacionalmente eficiente, que envolve apenas cálculos diretos em forma fechada a cada instante de tempo. É demonstrado que o algoritmo possui arrependimento sublinear em relação à sequência de referência dinâmica e violações de restrição sublinerares, desde que a deriva da sequência de referência seja sublinear, ou em outras palavras, que os problemas de otimização dinâmica subjacentes não variem drasticamente. Além disso, investigamos o cenário do feedback de bandit, no qual, após uma ação ser escolhida, apenas os valores da função objetivo e das funções de restrição em vários pontos aleatórios próximos à ação são anunciados ao agente. Uma versão bandit do algoritmo online é proposta e também estabelecemos seu arrependimento esperado sublinear e violações de restrição esperadas sublinerares sob a suposição de que a deriva da sequência de referência é sublinear. Finalmente, dois exemplos numéricos, nomeadamente programação quadrática online e regressão logística online, são apresentados para corroborar a eficácia dos algoritmos propostos e confirmar as garantias teóricas.