Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

Resumo Técnico: Sortimento Dinâmico Baseado em Dados em Plataformas Online: Aprendendo sobre Dois Lados

Formulação do Problema
O artigo aborda um problema de seleção de sortimento dinâmico em uma plataforma de serviço de dois lados operando sob informação incompleta. Diferente dos problemas de sortimento tradicionais, onde um tomador de decisão seleciona produtos para maximizar a receita baseando-se apenas nas preferências dos clientes, este cenário envolve participantes "ativos" tanto no lado da demanda (clientes) quanto no da oferta (vendedores).

O sistema opera em tempo discreto ao longo de um horizonte de $T$ períodos. A plataforma gerencia um conjunto de $N$ vendedores e encontra uma sequência de clientes que chegam com tipos heterogêneos. Em cada período, o gerente da plataforma seleciona um sortimento (um subconjunto de vendedores de tamanho no máximo $B$) para exibir a um cliente que chega. O cliente então escolhe, no máximo, um vendedor do sortimento exibido de acordo com um modelo de escolha Multinomial Logit (MNL), regido por parâmetros de preferência desconhecidos $v_{z,i}$ (onde $z$ é o tipo de cliente e $i$ é o vendedor).

Crucialmente, uma transação não é finalizada imediatamente após a escolha do cliente. Em vez disso, a proposta do cliente é mantida por uma duração fixa de $K$ períodos. Ao final de cada época (um bloco de $K$ períodos), os vendedores revisam as propostas que receberam e decidem se aceitam, no máximo, um cliente, com base em seus próprios parâmetros de preferência MNL desconhecidos $u_{i,z}$. Uma transação (e a subsequente recompensa) ocorre apenas se um vendedor aceitar uma proposta. O objetivo do gerente da plataforma é maximizar a recompensa total esperada ao longo do horizonte de planejamento.

O desafio central é o Aprendizado de Duas Vias (Two-Way Learning): a plataforma não conhece os parâmetros de escolha nem dos clientes ($V$) nem dos vendedores ($U$) e deve aprendê-los dinamicamente enquanto simultaneamente toma decisões de sortimento. Isso difere da literatura existente, que tipicamente assume aprendizado de uma via (apenas as preferências do cliente são desconhecidas) ou realização imediata de recompensa.

Metodologia
Os autores propõem um algoritmo online baseado em dados chamado TWL-UCB (Two-Way Learning via Upper Confidence Bound). O algoritmo é projetado para equilibrar exploração e explotação, lidando com a estrutura de feedback assíncrona de um mercado de dois lados.

1. Estimativas de Limite Superior de Confiança (UCB): O algoritmo mantém estimativas UCB tanto para os parâmetros de preferência do cliente ($v_{z,i}$) quanto para os parâmetros de preferência do vendedor ($u_{i,z}$).
   • Atualizações do Cliente (Passo II): Após cada período, a plataforma atualiza as estimativas do cliente com base nas escolhas observadas (propostas) dentro dos sortimentos oferecidos.
   • Atualizações do Vendedor (Passo III): As estimativas do vendedor são atualizadas apenas ao final de cada época ($K$ períodos), com base nas decisões de correspondência observadas (aceites/rejeições) pelos vendedores.
2. Otimização do Sortimento (Passo I): Em cada período, a plataforma seleciona um sortimento que maximiza o aumento marginal esperado de correspondências. Esta métrica, denotada como $\Delta_M$, captura o ganho esperado em correspondências para a época atual, dado o estado atual das propostas e as estimativas UCB de ambos os parâmetros de preferência (cliente e vendedor).
3. Minimização do Arrependimento (Regret): O desempenho é avaliado usando o arrependimento (regret), definido como a diferença entre a recompensa total alcançada por uma política clairvoyant (que conhece todos os parâmetros e sequências de chegada) e a recompensa alcançada pelo algoritmo proposto.

Principais Resultados e Contribuições Teóricas
O artigo estabelece a otimalidade teórica do algoritmo TWL-UCB através do correspondente de limites superior e inferior de arrependimento:

• Limite Superior (Teorema 1): Os autores provam que o arrependimento de pior caso do algoritmo TWL-UCB cresce polilogaritmicamente com o tempo: $O(\log^2(NT))$. Esta é uma melhoria significativa em relação aos limites de arrependimento $\tilde{O}(\sqrt{T})$ encontrados na literatura de sortimento dinâmico existente que foca em aprendizado de uma via.
• Limite Inferior (Teorema 2): O artigo deriva um limite inferior correspondente, mostrando que, para qualquer política admissível, o arrependimento de pior caso é de pelo menos $\tilde{\Omega}(\log^2(NT))$.
• Otimidade de Taxa: O alinhamento dos limites superior e inferior estabelece que o algoritmo TWL-UCB é de taxa ótima para o problema de Aprendizado de Duas Vias.
• Descobertas de Simulação:
  • O algoritmo TWL-UCB supera consistentemente versões adaptadas de algoritmos de aprendizado de uma via (especificamente, o algoritmo UCB de Agrawal et al., 2019) em cenários de dois lados. Estes últimos falham porque não conseguem contabilizar o feedback atrasado e a incerteza do lado do vendedor.
  • O estudo identifica um efeito de limiar em relação ao tamanho do sortimento: aumentar o tamanho máximo do sortimento ($B$) além de um certo ponto (observado em torno de 30 nas simulações) gera retornos decrescentes na recompensa total da plataforma.

Extensões e Robustez
O artigo analisa duas extensões para demonstrar a robustez do algoritmo:

1. Transparência de Informação: O algoritmo mantém seu limite de arrependimento $O(\log^2(NT))$ mesmo se o gerente da plataforma compartilhar apenas informações parciais específicas do cliente com os vendedores (Teorema 3).
2. Recompensas Dependentes do Cliente: O limite de arrependimento mantém-se mesmo quando a recompensa por uma correspondência bem-sucedida depende do tipo específico de cliente correspondido, em vez de um valor fixo por época (Teorema 4).

Significância e Alegações
Os autores afirmam que este é o primeiro estudo a formular e analisar um problema de sortimento dinâmico onde o tomador de decisão deve aprender os parâmetros de escolha de ambos os lados de um mercado de dois lados simultaneamente.

A significância do trabalho reside na:

• Novidade do Problema: Ir além do aprendizado de uma via para um framework de "Aprendizado de Duas Vias" que reflete a natureza ativa dos participantes em plataformas de serviços modernas (ex: Airbnb, Upwork, HomeAdvisor).
• Avanço Algorítmico: Demonstrar que o arrependimento polilogarítmico é alcançável neste complexo cenário de feedback atrasado, enquanto problemas de aprendizado de uma via tipicamente sofrem com arrependimento de raiz quadrada.
• Insight Prático: Destacar que algoritmos projetados para aprendizado de um lado são ineficazes em ambientes de dois lados e que os gerentes de plataforma devem ser cautelosos ao expandir os tamanhos de sortimento devido aos retornos decrescentes.

O artigo conclui que o proposto algoritmo TWL-UCB fornece uma solução teoricamente ótima e robusta para gerentes de plataforma que operam sob informação incompleta em mercados de dois lados.