Nous abordons le problème ardu de la segmentation d'objets vidéo zéro-shot (VOS). Il s'agit de segmenter et de suivre plusieurs objets en mouvement au sein d'une vidéo de manière entièrement automatique, sans aucune initialisation manuelle. Nous traitons ce problème comme un problème de regroupement en exploitant des propositions d'objets et en effectuant une inférence conjointe sur le regroupement dans l'espace et le temps. Nous proposons une architecture de réseau permettant d'effectuer de manière opérationnelle la sélection des propositions et le regroupement conjoint. De manière cruciale, nous montrons ensuite comment entraîner ce réseau avec l'apprentissage par renforcement afin qu'il apprenne à réaliser la séquence optimale de décisions de regroupement pour segmenter l'intégralité de la vidéo. Contrairement aux techniques supervisées standards, cela nous permet également d'optimiser directement les métriques basées sur le chevauchement non différentiable utilisées pour évaluer la VOS. Nous démontrons que la méthode proposée, que nous appelons ALBA, surpasses l'état de l'art précédent sur trois benchmarks : DAVIS 2017 [2], FBMS [20] et Youtube-VOS [27].