This happened to me yesterday, was watching a movie when the video froze and a few seconds later the TV rebooted. Was greeted with the exclamation symbol and a URL support.apple.com/appletv/restore. I tried the power cycling trick but that didn’t work. So booked a session at the Apple Store.
The tech at the genius bar had some useful info. He said the restoration method now uses the Ethernet port. He confirmed the bootloader will try to redownload the OS via the Ethernet port. However he didn’t clarify if this was downloaded from the Internet or from the Apple Store’s LAN servers.
He plugged a Cat6 cable into the GigE port, unplugged the power cord, counted to 15, then plugged the power back in while holding Menu + Home on the remote at the same time.
Unfortunately that didn’t work either so he handed me a new ATV 4K. Luckily mine was still under warranty. But if anybody else has this happen out of warranty give the Ethernet method a try.