[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.

[pt] Essa tese é composta por dois capítulos. O primeiro deles refere-se ao problema de aprendizado sequencial, útil em diversos campos de pesquisa e aplicações práticas. Exemplos incluem problemas de apreçamento dinâmico, desenhos de leilões e de incentivos, além de programas e tratamentos sequenciais. Neste capítulo, propomos a extensão de uma das mais populares regras de aprendizado, epsilon-greedy, para contextos de alta-dimensão, levando em consideração uma diretriz conservadora. Em particular, nossa proposta consiste em alocar parte do tempo que a regra original utiliza na adoção de ações completamente novas em uma busca focada em um conjunto restrito de ações promissoras. A regra resultante pode ser útil para aplicações práticas nas quais existem restrições suaves à adoção de ações não-usuais, mas que eventualmente, valorize surpresas positivas, ainda que a uma taxa decrescente. Como parte dos resultados, encontramos limites plausíveis, com alta probabilidade, para o remorso cumulativo para a regra epsilon-greedy conservadora em alta-dimensão. Também, mostramos a existência de um limite inferior para a cardinalidade do conjunto de ações viáveis que implica em um limite superior menor para o remorso da regra conservadora, comparativamente a sua versão não-conservadora. Adicionalmente, usuários finais possuem suficiente flexibilidade em estabelecer o nível de segurança que desejam, uma vez que tal nível não impacta as propriedades teóricas da regra de aprendizado proposta. Ilustramos nossa proposta tanto por meio de simulação, quanto por meio de um exercício utilizando base de dados de um problema real de sistemas de classificação. Por sua vez, no segundo capítulo, investigamos efeitos de tratamento determinísticos quando a regra de aloção é complexa e desconhecida, talvez por razões éticas, ou para evitar manipulação ou competição desnecessária. Mais especificamente, com foco na metodologia de regressão discontínua sharp, superamos a falta de conhecimento de pontos de corte na alocação de unidades, pela implementação de uma floresta de árvores de classificação, que também utiliza aprendizado sequencial na sua construção, para garantir que, assintoticamente, as regras de alocação desconhecidas sejam identificadas corretamente. A estrutura de árvore também é útil nos casos em que a regra de alocação desconhecida é mais complexa que as tradicionais univariadas. Motivado por exemplos da vida prática, nós mostramos nesse capítulo que, com alta probabilidade e baseado em premissas razoáveis, é possível estimar consistentemente os efeitos de tratamento sob esse cenário. Propomos ainda um algoritmo útil para usuários finais que se mostrou robusto para diferentes especificações e que revela com relativa confiança a regra de alocação anteriormente desconhecida. Ainda, exemplificamos os benefícios da metodologia proposta pela sua aplicação em parte do P900, um programa governamental Chileno de suporte para escolas, que se mostrou adequado ao cenário aqui estudado. / [en] Sequential learning problems are common in several fields of research and practical applications. Examples include dynamic pricing and assortment, design of auctions and incentives and permeate a large number of sequential treatment experiments. In this essay, we extend one of the most popular learning solutions, the epsilon-greedy heuristics, to high-dimensional contexts considering a conservative directive. We do this by allocating part of the time the original rule uses to adopt completely new actions to a more focused search in a restrictive set of promising actions. The resulting rule might be useful for practical applications that still values surprises, although at a decreasing rate, while also has restrictions on the adoption of unusual actions. With high probability, we find reasonable bounds for the cumulative regret of a conservative high-dimensional decaying epsilon-greedy rule. Also, we provide a lower bound for the cardinality of the set of viable actions that implies in an improved regret bound for the conservative version when compared to its non-conservative counterpart. Additionally, we show that end-users have sufficient flexibility when establishing how much safety they want, since it can be tuned without impacting theoretical properties. We illustrate our proposal both in a simulation exercise and using a real dataset. The second essay studies deterministic treatment effects when the assignment rule is both more complex than traditional ones and unknown to the public perhaps, among many possible causes, due to ethical reasons, to avoid data manipulation or unnecessary competition. More specifically, sticking to the well-known sharp RDD methodology, we circumvent the lack of knowledge of true cutoffs by employing a forest of classification trees which also uses sequential learning, as in the last essay, to guarantee that, asymptotically, the true unknown assignment rule is correctly identified. The tree structure also turns out to be suitable if the program s rule is more sophisticated than traditional univariate ones. Motivated by real world examples, we show in this essay that, with high probability and based on reasonable assumptions, it is possible to consistently estimate treatment effects under this setup. For practical implementation we propose an algorithm that not only sheds light on the previously unknown assignment rule but also is capable to robustly estimate treatment effects regarding different specifications imputed by end-users. Moreover, we exemplify the benefits of our methodology by employing it on part of the Chilean P900 school assistance program, which proves to be suitable for our framework.